2008年8月30日 星期六

中置轉成後置

code
package javahomework;

import javax.swing.JOptionPane;

class postfix {
 private char stack[], z[];
 private int pri[] = { 0, 1, 1, 2, 2, 3 };
 private char oper[] = { '(', '+', '-', '*', '/', '^' };
 private int top, n, a;
 private String postfix = "";
 private char x[], y;

 public postfix() {
  n = 50;
  top = 0;
  a = 0;
  stack = new char[n];
  z = new char[n];
 }

 public String infix_to_postfix(String infix) {
  int i = 0, j = infix.length();
  x = infix.toCharArray();
  for (i = 0; i < j; i++) {
   switch (x[i]) {
   case '(':
    push(x[i]);
    break;
   case ')':
    y = pop();
    while (!empty() && y != '(') {
     z[a++] = y;
     y = pop();
    }
    break;
   case '+':
   case '-':
   case '*':
   case '/':
   case '^':
    y = top();
    while (pre(y) >= pre(x[i])) {
     z[a++] = pop();
     y = top();
    }
    push(x[i]);
    break;
   default:
    z[a++] = x[i];
   }
  }
  while (!empty()) {
   z[a++] = pop();
  }
  for (i = 0; i <= a - 2; i++) {

   postfix += z[i];
   postfix += " ";
  }
  return postfix;
 }

 private boolean empty() {
  return (top < 0) ? true : false;
 }

 private boolean full() {
  return (top >= n - 1) ? true : false;
 }

 private void push(char sta) {
  stack[++top] = sta;
 }

 private char pop() {
  return stack[top--];
 }

 private char top() {
  return stack[top];
 }

 private int pre(char op) {
  for (int i = 0; i < 6; i++)
   if (oper[i] == op)
    return pri[i];
  return -1;
 }

 private void check(char x, char y) {
  y = top();
  while (pre(y) >= pre(x)) {
   postfix += pop();
   y = top();
  }
  push(x);
 }

}

public class HW18 {

 public static void main(String arg[]) {
  String input = JOptionPane.showInputDialog(null,
    "Please input string (ex.1+2-3)");
  postfix p = new postfix();
  JOptionPane.showMessageDialog(null, 
    String.valueOf(p.infix_to_postfix(input)));
 }
}

沒有留言: