这里theStack 只是存放了 操作符 感觉写的也不是很好..
// infix.java
// converts infix arithmetic expressions to postfix
// to run this program: C>java InfixApp
import java.io.*; // for I/Oclass StackX{private int maxSize;private char[] stackArray;private int top;
//--------------------------------------------------------------public StackX(int s) // constructor{maxSize = s;stackArray = new char[maxSize];top = -1;}
//--------------------------------------------------------------public void push(char j) // put item on top of stack{ stackArray[++top] = j; }
//--------------------------------------------------------------public char pop() // take item from top of stack{ return stackArray[top--]; }
//--------------------------------------------------------------public char peek() // peek at top of stack{ return stackArray[top]; }
//--------------------------------------------------------------public boolean isEmpty() // true if stack is empty{ return (top == -1); }
//-------------------------------------------------------------public int size() // return size{ return top+1; }
//--------------------------------------------------------------public char peekN(int n) // return item at index n{ return stackArray[n]; }
//--------------------------------------------------------------public void displayStack(String s){System.out.print(s);System.out.print("Stack (bottom-->top): ");for(int j=0; j<size(); j++){System.out.print( peekN(j) );System.out.print(' ');}System.out.println("");}
//--------------------------------------------------------------} // end class StackXclass InToPost // infix to postfix conversion{private StackX theStack;private String input;private String output = "";
//--------------------------------------------------------------public InToPost(String in) // constructor{input = in;int stackSize = input.length();theStack = new StackX(stackSize);}
//--------------------------------------------------------------public String doTrans() // do translation to postfix{for(int j=0; j<input.length(); j++) // for each char{char ch = input.charAt(j); // get ittheStack.displayStack("For "+ch+" "); // *diagnostic*switch(ch){case '+': // it's + or -case '-':gotOper(ch, 1); // go pop operatorsbreak; // (precedence 1)case '*': // it's * or /case '/':gotOper(ch, 2); // go pop operatorsbreak; // (precedence 2)case '(': // it's a left parentheStack.push(ch); // push itbreak;case ')': // it's a right parengotParen(ch); // go pop operatorsbreak;default: // must be an operandoutput = output + ch; // write it to outputbreak;} // end switch} // end forwhile( !theStack.isEmpty() ) // pop remaining opers{theStack.displayStack("While "); // *diagnostic*output = output + theStack.pop(); // write to output}theStack.displayStack("End "); // *diagnostic*return output; // return postfix} // end doTrans()
//--------------------------------------------------------------public void gotOper(char opThis, int prec1){ // got operator from inputwhile( !theStack.isEmpty() ){char opTop = theStack.pop();if( opTop == '(' ) // if it's a '('{theStack.push(opTop); // restore '('break;}else // it's an operator{int prec2; // precedence of new opif(opTop=='+' || opTop=='-') // find new op precprec2 = 1;elseprec2 = 2;if(prec2 < prec1) // if prec of new op less{ // than prec of oldtheStack.push(opTop); // save newly-popped opbreak;}else // prec of new not lessoutput = output + opTop; // than prec of old} // end else (it's an operator)} // end whiletheStack.push(opThis); // push new operator} // end gotOp()
//--------------------------------------------------------------public void gotParen(char ch){ // got right paren from inputwhile( !theStack.isEmpty() ){char chx = theStack.pop();if( chx == '(' ) // if popped '('break; // we're doneelse // if popped operatoroutput = output + chx; // output it} // end while} // end popOps()
//--------------------------------------------------------------} // end class InToPostclass InfixApp{public static void main(String[] args) throws IOException{String input, output;while(true){System.out.print("Enter infix: ");System.out.flush();input = getString(); // read a string from kbdif( input.equals("") ) // quit if [Enter]break;// make a translatorInToPost theTrans = new InToPost(input);output = theTrans.doTrans(); // do the translationSystem.out.println("Postfix is " + output + '\n');} // end while} // end main()
//--------------------------------------------------------------public static String getString() throws IOException{InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}
//--------------------------------------------------------------} // end class InfixApp// postfix.java
// parses postfix arithmetic expressions
// to run this program: C>java PostfixApp
import java.io.*; // for I/Oclass StackX{private int maxSize;private int[] stackArray;private int top;
//--------------------------------------------------------------public StackX(int size) // constructor{maxSize = size;stackArray = new int[maxSize];top = -1;}
//--------------------------------------------------------------public void push(int j) // put item on top of stack{ stackArray[++top] = j; }
//--------------------------------------------------------------public int pop() // take item from top of stack{ return stackArray[top--]; }
//--------------------------------------------------------------public int peek() // peek at top of stack{ return stackArray[top]; }
//--------------------------------------------------------------public boolean isEmpty() // true if stack is empty{ return (top == -1); }
//--------------------------------------------------------------public boolean isFull() // true if stack is full{ return (top == maxSize-1); }
//--------------------------------------------------------------public int size() // return size{ return top+1; }
//--------------------------------------------------------------public int peekN(int n) // peek at index n{ return stackArray[n]; }
//--------------------------------------------------------------public void displayStack(String s){System.out.print(s);System.out.print("Stack (bottom-->top): ");for(int j=0; j<size(); j++){System.out.print( peekN(j) );System.out.print(' ');}System.out.println("");}
//--------------------------------------------------------------} // end class StackXclass ParsePost{private StackX theStack;private String input;
//--------------------------------------------------------------public ParsePost(String s){ input = s; }
//--------------------------------------------------------------public int doParse(){theStack = new StackX(20); // make new stackchar ch;int j;int num1, num2, interAns;for(j=0; j<input.length(); j++) // for each char,{ch = input.charAt(j); // read from inputtheStack.displayStack(""+ch+" "); // *diagnostic*if(ch >= '0' && ch <= '9') // if it's a numbertheStack.push( (int)(ch-'0') ); // push itelse // it's an operator{num2 = theStack.pop(); // pop operandsnum1 = theStack.pop();switch(ch) // do arithmetic{case '+':interAns = num1 + num2;break;case '-':interAns = num1 - num2;break;case '*':interAns = num1 * num2;break;case '/':interAns = num1 / num2;break;default:interAns = 0;} // end switchtheStack.push(interAns); // push result} // end else} // end forinterAns = theStack.pop(); // get answerreturn interAns;} // end doParse()} // end class ParsePostclass PostfixApp{public static void main(String[] args) throws IOException{String input;int output;while(true){System.out.print("Enter postfix: ");System.out.flush();input = getString(); // read a string from kbdif( input.equals("") ) // quit if [Enter]break;// make a parserParsePost aParser = new ParsePost(input);output = aParser.doParse(); // do the evaluationSystem.out.println("Evaluates to " + output);} // end while} // end main()
//--------------------------------------------------------------public static String getString() throws IOException{InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}
//--------------------------------------------------------------} // end class PostfixApp