©2020-2024 ioDraw All rights reserved,
Privacy Policy
应用3中计算的是后缀表达式，需要先将中缀表达式转换为后缀表达式再计算，整个表达式会扫描两次，下面我们实现只扫描一次实现计算中缀表达式。‘
解决这个问题需要两个栈，一个是操作数栈，一个是运算符栈。 一、算法逻辑 1）创建操作数栈 2）创建运算符栈
我们定义运算操作为操作数栈中弹出两个元素，运算符栈中弹出元素，进行计算后，结果压入操作数栈。
3）扫描中缀表达式，进行遍历 a.如果字符是操作数，则压入操作数栈
b.如果左括号，压入运算符栈。
c.如果是右括号，循环执行运算操作，直至弹出的是左括号。
d.如果是运算符，如果运算符栈不为空，则判断运算栈栈顶运算符是不否为左括号，且优先级大于当前运算符，则执行运算操作。当前运算符压入运算符栈。
4）扫描完后，如果运算符栈不为空，就循环运算操作执行，直至运算符栈为空。操作数栈中最后栈顶元素就是运算结果。 二、算法实现
1 2 import java.util.Stack; 3 4 /**计算后缀表达式 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
//创建操作数栈 16 Stack<Integer> stack = new Stack<>(); 17 18
//创建运算符栈 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
//如果是操作数就压入到操作数栈 28 stack.push(Integer.valueOf(s)); 29
}else if(OperatorEnum.isLeftSign(s)){ 30 31 //如果是左括号，则忽略
32 continue; 33 }else if(OperatorEnum.isRightSign(s
)){ 34 35 //如果是右括号，就弹出两个操作数，弹出一个运算符，计算之后，结果压入操作数栈 36
//弹出操作数 37 Integer a = stack.pop(); 38
Integer b = stack.pop(); 39 40 //弹出元素符 41
String operator = stack1.pop(); 42 stack.push(useOperator(
operator,b,a)); 43 }else{ 44 45 //如果是运算符 46
if(!stack1.isEmpty()){ 47 48
//如果运算符栈不为空，且上一个运算符的优先级比当前运算符优先级大，就执行运算操作 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
//当前运算符压入运算符栈 59 stack1.push(s); 60
} 61 } 62 63 //遍历完后，如果运算符栈不为空，就循环执行运算操作，直至操作符栈为空 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 三、算法实现跟踪 我们假设计算 (1+2)*5+(3*6-2)*2
字符 操作 表达式 操作数栈 运算符栈
（ 压入运算符栈 (
1 压入操作数栈 1 (
+ 运算栈为空，压入运算符栈 1 (+
2 压入操作数栈 1 2 (+
） 弹出两个操作数，弹出一个运算符，执行运算，结果压入操作数栈 1+2 3
* 运算栈为空，压入运算符栈 3
5 压入操作数栈 3 5
+ 判断上一个运算符是否大于当前运算符优先级，大于, 弹出两个操作数，弹出上 一个运算符，执行运算，结果压入操作数栈，当前运算符压入运算符栈
3 * 5 = 15 15 +
（ 忽略 15 (+
3 压入操作数栈 15 3 (+
* 判断上一个运算符是否大于当前运算符优先级，不大于, 当前运算符压入运算符栈 15 3 9+ *
6 压入操作数栈 15 3 6 （+ *
- 判断上一个运算符是否大于当前运算符优先级，大于, 弹出两个操作数，弹出上 一个运算符，执行运算，结果压入操作数栈，当前运算符压入运算符栈
3*6=18 15 18 （+ -
2 压入操作数栈 15 18 2 （+ -
) 弹出两个操作数，弹出一个运算符，执行运算，结果压入操作数栈 18-2 = 16 15 16 +
* 判断上一个运算符是否大于当前运算符优先级，不大于, 当前运算符压入运算符栈 15 16 + *
2 压入操作数栈 15 16 2 + *
输入结束 循环执行运算操作 16*2 = 32
15+32 = 47 47