An overview of the

Prefix, infix, and postfix expressions are usually determined by the position of the operator. Before we understand what prefix and postfix expressions are, we can look at what infix expressions are. Look at the following example: (3+4)* 5-6 this is what we normally see.

Although infix expression in accordance with our People’s Daily habits of thinking, but the computer in the infix expression, you need to use this tree data structure (thinking, because here, including the concept of the parentheses), if the expression is too complex, so the height of the tree are high, greatly increases the time complexity and space complexity. If converted to a linear structure, the efficiency becomes much higher, so the infix expression needs to be converted to prefix or suffix expression, and then rely on the stack of linear data structure to calculate. In general computer storage is basically converted into postfix expression, and then to evaluate.

Prefix expression

Prefix expressions, also known as Polish expressions, feature operators that precede operands. So for example, if you prefix 3 plus 4 x 5 minus 6, that’s minus x plus 3, 4, 5, 6.

How do infix expressions become prefix expressions

*(1) Initialize two stacks: the operator stack S1 and the intermediate result stack S2; * (2) Scan infix expressions from right to left; * (3) When it encounters an operand, press it into S2; * (4) When encountering an operator, compare its priority with that of S1 at the top of the stack: * (4-1) If S1 is empty, the operator is directly pushed onto the stack; * (4-2) Otherwise, if the priority is higher or equal to that of the top of the stack operator (higher in postfix expressions, no equal) or if the top of the stack operator is the closing parenthesis ") ", the operator is also pushed into S1; * (4-3) Otherwise, pop the top of S1 and push it into S2, and go to (4-1) again to compare with the new top of S1; * (5) when the parenthesis is encountered: * (5-1) if it is the right parenthesis ") ", then directly pressed into S1; * (5-2) If it is the open parenthesis "(", the operator at the top of S1 stack is successively popped and pressed into S2 until the close parenthesis is encountered, at which point the pair of parentheses is discarded * (6) Repeat steps (2) through (5) until the leftmost part of the expression; * (7) Pop up the remaining operators in S1 and press them into S2; * (8) Pop up elements in S2 in turn and output, the result is the prefix expression corresponding to the infix expression. * (suffix expression here to reverse the string output, here directly output can be)Copy the code

Here are the steps to perform the transformation:

Private static String zhong2Qian(String expression) {//(1) initialize two stacks: S1 and S2; Stack<Character> ops = new Stack<>(); Stack<Character> resultValues = new Stack<>(); //(2) scan infix expressions from right to left; Expression = reverseString(expression); char[] chars = expression.toCharArray();for(char theChar: chars) {//(3) when the operand is encountered, press it into S2;if(Character.isDigit(theChar)) resultValues.push(theChar); //(4) compare the priority of the S1 top operator with that of the S1 top operator:else if (theChar == '+' || theChar == The '-' || theChar == The '*' || theChar == '/') { dealTheChar(ops, resultValues, theChar); } //(5-1);else if (theChar == ') ') ops.push(theChar); //(5-2) If the left parenthesis is "(", then the top operator of S1 is displayed and S2 is pressed until the right parenthesis is encountered, at which point the pair of parentheses is discarded;else if (theChar == '(') {
                char opsChar = ops.pop();
                while(opsChar ! = (') ')) { resultValues.push(opsChar); opsChar = ops.pop(); }}} //(7) pop up the remaining operators in S1 and press them into S2;while(! ops.empty()) { resultValues.push(ops.pop()); } //(8) pop up elements in S2 in turn and output, the result is the prefix expression corresponding to the infix expression. StringBuilder exp = new StringBuilder();while(! resultValues.empty()) exp.append(resultValues.pop());return exp.toString();
    }
Copy the code

Postfix expression

Postfix expressions, also known as inverse Polish expressions, are similar to prefix expressions except that the operator is placed after the operator and the conversion scan the expression from left to right. This is also the main way arithmetic expressions are stored in computers.

How do infix expressions become prefix expressions

/** * Convert an infix expression to a suffix expression: Similar to converting an infix expression to a prefix expression, follow these steps: * (1) Initialize two stacks: the operator stack S1 and the intermediate result stack S2; * (2) Scan infix expressions from left to right; * (3) When it encounters an operand, press it into S2; * (4) When encountering an operator, compare its priority with that of the top of the stack operator S1: * (4-1) If S1 is empty or the top of the stack operator is an open parenthesis "(", the operator is directly pushed onto the stack; * (4-2) Otherwise, if the priority is higher than that of the top of the stack, the operator is also pushed into S1 (note that the conversion to a prefix expression is higher or the same, but the same case is not included here); * (4-3) Otherwise, pop the top of S1 and push it into S2, and go to (4-1) again to compare with the new top of S1; * (5) When the parenthesis is encountered: * (5-1) If the opening parenthesis is "(", then directly pressed into S1; * (5-2) If it is the close parenthesis ") ", the operator at the top of S1 stack will be popped successively and S2 will be pressed until the open parenthesis is encountered, at which point the pair of parentheses will be discarded; * (6) Repeat steps (2) through (5) until the rightmost part of the expression; * (7) Pop up the remaining operators in S1 and press them into S2; * (8) Pop up the elements in S2 in turn and output, and the reverse order of the result is the suffix expression corresponding to the infix expression (no reverse order is required when converting to the prefix expression). * @return* /Copy the code

Calculations can be complicated, so here are two examples:

(1): infix expression 1+((2 + 3) x 4)-5

(2): infix expression (3+ 4) x 5-6

The code implementation is as follows:

Private static String zhong2hou(String expression) {//(1) initialize two stacks: S1 and S2; Stack<Character> ops = new Stack<>(); Stack<Character> resultValues = new Stack<>(); char[] chars = expression.toCharArray(); //(2) scan infix expressions from left to right;for(char theChar: chars){//(3) when the operand is encountered, press it into S2;if(Character.isDigit(theChar)) resultValues.push(theChar); //(4) compare the priority of the S1 top operator with that of the S1 top operator:else if (theChar == '+' || theChar == The '-' || theChar == The '*' || theChar == '/') dealTheChar(ops,resultValues,theChar); //(5) (S1); //(5) (S1) (S1);else if (theChar == '(') ops.push(theChar); //(5-2) if it is the close parenthesis ") ", the top operator of S1 is displayed and S2 is pressed until the open parenthesis is encountered, at which point the parenthesis pair is discarded;else if (theChar == ') '){
                char opsChar  = ops.pop();
                while(opsChar ! ='(') { resultValues.push(opsChar); opsChar = ops.pop(); }}} //(7) pop up the remaining operators in S1 and press them into S2;while(! ops.isEmpty()) resultValues.push(ops.pop()); //(8) Pop up the elements in S2 and output the result in reverse order, which is the suffix expression corresponding to the infix expression (reverse order is not required when converting to the prefix expression). StringBuilder exp = new StringBuilder();while(! resultValues.empty()) exp.append(resultValues.pop());returnreverseString(exp.toString()); } private static void dealTheChar(Stack<Character> ops, Stack<Character> values, char theChar) {private static void dealTheChar(Stack<Character> ops, Stack<Character> resultValues, char theChar) { The operator is pushed directly onto the stack;if (ops.empty()) {
            ops.push(theChar);
            return; } char popTheChar = ops.pop().charValue(); //(4-1) If S1 is empty, or the top of the stack operator is a close parenthesis "(", then the operator is directly pushed onto the stack; //(4-2) otherwise, if the priority is higher than that of the top of the stack, the operator is also pushed into S1.if (popTheChar == '('|| getPriorityValue(theChar) > getPriorityValue(popTheChar)) { ops.push(popTheChar); ops.push(theChar); } //(4-3) otherwise, pop the operator at the top of S1 and push it into S2else{ resultValues.push(popTheChar); //, go to (4-1) again to compare with the new top-stack operator in S1; dealTheChar(ops, resultValues, theChar); }}Copy the code