application 3 The suffix expression is evaluated in , The infix expression needs to be converted to a suffix expression before calculation , The entire expression is scanned twice , Next, we implement scanning only once to calculate infix expressions .‘
Two stacks are needed to solve this problem , One is the stack of operands , One is the operator stack . One , Algorithmic logic 1） Creating an operands stack 2） Create operator stack
We define an operation as two elements that pop up in the stack of operands , Pop up elements in operator stack , After calculation , The result is pushed into the operands stack .
3） Scan infix expression , Traverse     a. If the character is an operand , Push operations
b. If the left bracket , Push operator stack .
c. If it's a right bracket , Loop operation , Until the left bracket pops up .
d. If it's an operator , If the operator stack is not empty , The operator at the top of the stack is left bracket , And the priority is greater than the current operator , The operation is performed . The current operator is pushed into the operator stack .
4） After scanning , If the operator stack is not empty , To perform a loop operation , Until the operator stack is empty . The last element at the top of the stack of operands is the result of the operation . Two , Algorithm implementation
1 2 import java.util.Stack; 3 4 /** Evaluate suffix expression 5 * Created by Administrator
on 2017/6/25 0025. 6 */ 7 public class Operator2Stack { 8    public static
void main(String[] args) { 9        String str = "(1+2)*5+(3*6+2)*2+(3*6-2)*3"
; 10        System.out.println(useNum(str)); 11   } 12    public static
int useNum(String str){ 13        char[] chars = str.toCharArray(); 14 15
// Creating an operands stack 16        Stack<Integer> stack = new Stack<>(); 17 18
// Create operator stack 19        Stack<String> stack1 = new Stack<>(); 20        for(
char c : chars){ 21            String s = String.valueOf(c); 22 23 24 25
if(!OperatorEnum.isOperator(s)){ 26 27
// If it's an operand, it's pushed into the stack of operands 28                stack.push(Integer.valueOf(s)); 29
}else if(OperatorEnum.isLeftSign(s)){ 30 31                // If it's a left bracket , Ignore
32                continue; 33           }else if(OperatorEnum.isRightSign(s
)){ 34 35                // If it's a right bracket , Just pop up two operands , Pop up an operator , After calculation , The result is pushed into the operands stack 36
// Eject operands 37                Integer a = stack.pop(); 38
Integer b = stack.pop(); 39 40                // Pop up element 41
String operator = stack1.pop(); 42                stack.push(useOperator(
operator,b,a)); 43           }else{ 44 45                // If it's an operator 46
if(!stack1.isEmpty()){ 47 48
// If the operator stack is not empty , And the priority of the previous operator is higher than that of the current operator , On the implementation of the operation 49                    String peek =
stack1.peek(); 50                    if(OperatorEnum.getOperatorLevel(s) <
OperatorEnum.getOperatorLevel(peek)){ 51                        peek = stack1.
pop(); 52                        Integer a = stack.pop(); 53
Integer b = stack.pop(); 54                        stack.push(
useOperator(peek,b,a)); 55                   } 56               } 57 58
// The current operator is pushed into the operator stack 59                stack1.push(s); 60
} 61       } 62 63        // After traversing , If the operator stack is not empty , Perform an operation on the loop , Until the operator stack is empty 64
while(!stack1.isEmpty()){ 65            String pop = stack1.pop(); 66
Integer a = stack.pop(); 67            Integer b = stack.pop(); 68
stack.push(useOperator(pop ,b,a)); 69       } 70        return stack.
pop(); 71   } 72    public static int useOperator(String operator, int a,int
b){ 73        if(operator.equals(OperatorEnum.PLUS_SIGN.getOpertor())){ 74
return a+b; 75       } 76        if(operator.equals(OperatorEnum.
MINUS.getOpertor())){ 77            return a-b; 78       } 79        if(
operator.equals(OperatorEnum.TIMES_SIGN.getOpertor())){ 80            return a
*b; 81       } 82        if(operator.equals(OperatorEnum.DIVISION_SIGN.
getOpertor())){ 83            return a/b; 84       } 85        return 0;
86   } 87 } 88 Three , Algorithm implementation tracking Let's assume the calculation (1+2)*5+(3*6-2)*2
character      operation      expression      Operands stack      Operator stack
（     Push operator stack     (
1     Push into the stack of operands      1 (
+     The operation stack is empty , Push operator stack   1 (+
2 Push into the stack of operands        1 2      (+
）     Pop up two operands , Pop up an operator , Perform the operation , The result is pushed into the operands stack 1+2     3
*     The operation stack is empty , Push operator stack       3
5 Push into the stack of operands        3 5
+     Determines whether the previous operator is greater than the current operator priority , greater than ,  Pop up two operands , Pop it up      An operator , Perform the operation , The result is pushed into the operands stack , The current operator is pushed into the operator stack
3 * 5  = 15     15 +
（     ignore        15      (+
3 Push into the stack of operands        15   3     (+
*     Determines whether the previous operator is greater than the current operator priority , No more than ,  The current operator is pushed into the operator stack   15    3 9+  *
6 Push into the stack of operands        15 3 6     （+  *
-     Determines whether the previous operator is greater than the current operator priority , greater than ,  Pop up two operands , Pop it up      An operator , Perform the operation , The result is pushed into the operands stack , The current operator is pushed into the operator stack
3*6=18     15 18     （+  -
2     Push into the stack of operands        15  18  2 （+  -
)     Pop up two operands , Pop up an operator , Perform the operation , The result is pushed into the operands stack 18-2 = 16     15 16     +
* Determines whether the previous operator is greater than the current operator priority , No more than ,  The current operator is pushed into the operator stack   15  16 + *
2 Push into the stack of operands        15  16  2 + *
End of input      Loop operation      16*2 = 32
15+32 = 47       47

Technology
Daily Recommendation
views 12
views 11