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