实现带括号的四则运算表达式的计算
本题源于找暑期实习携程二面当时的手撕题目，当时比较懵逼，没有撕出来
1
2
3
| 题目描述:
利用栈或者队列求解:
1+((2+3)×4)-5
|
分析:我们以前做过如何用单个栈求解逆波兰表达式的值，本题给出的是一个中缀表达式，逆波兰表达式是后缀表达式的形式
比如:题目中的表达式对应的后缀表达形式为:123+4×+5-
所以本题首先需要解决的问题是：
- 如何将一个中缀表达式转换为后缀表达式
- 如何求解后缀表达式的值
中缀表达式转后缀表达式
利用一个栈一个队列即可，定义一个栈stack和一个队列queue，然后遍历中缀表达式，碰到数字，直接将其加入队列queue，碰到非数字字符，则根据实际情况需要做如下操作：
- 如果当前栈
stack为空或者stack栈顶元素为(，则直接将当前字符加入栈stack
- 如果当前字符的优先级大于栈
stack栈顶字符的优先级，则也直接将当亲字符加入栈stack
- 否则，不断弹出栈
statck栈顶的字符直到栈顶字符的优先级小于当前字符或者栈顶字符为’(‘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| public int getPriority(char c){
int priority=0;
switch (c){
case '+':priority=1;break;
case '-':priority=1;break;
case '×':priority=2;break;
case '/':priority=2;break;
}
return priority;
}
public List<String> inPrefix2postPrefix(String str){
List<String> resultList = new ArrayList<>();
Stack<Character> opStack = new Stack<>();
int index=0;
while (index< str.length()){
char c = str.charAt(index);
if(c>='0' && c<='9'){
StringBuilder sb = new StringBuilder();
while (index<str.length() && (str.charAt(index)>='0' && str.charAt(index)<='9')){
sb.append(str.charAt(index));
index+=1;
}
resultList.add(sb.toString());
}else{
if(c=='(' || opStack.isEmpty()){
opStack.push(c);
} else if (c==')') {
while (!(opStack.peek()=='(')){
resultList.add(opStack.pop()+"");
}
opStack.pop();
} else if(opStack.peek()=='('){
opStack.push(c);
}else if(getPriority(opStack.peek())<getPriority(c)){
opStack.push(c);
}else{
while (getPriority(c)<=getPriority(opStack.peek())){
resultList.add(opStack.pop()+"");
if(opStack.size()==0 || opStack.peek()=='(') break;
}
opStack.push(c);
}
index+=1;
}
}
while (!opStack.isEmpty()){
resultList.add(opStack.pop()+"");
}
return resultList;
}
|
字符的优先级
- ‘)’优先级最高
- ‘×’与’/‘的优先级要高于’+’和’-‘
- ‘(‘的优先级最低
后缀表达式求值
利用单个栈stack即可解决，碰到数字，则直接入栈，碰到字符，则弹出栈中的两个数字，根据运算符类型进行求解，再将运算结果加入栈中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public int calbyPostPrefix(List<String> postPrefixList){
Stack<Integer> stack = new Stack<>();
for(String item:postPrefixList){
if(item.equals("+") || item.equals("-") || item.equals("×") || item.equals("/")){
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(cal(num1,num2,item));
}else{
stack.push(Integer.parseInt(item));
}
}
return stack.peek();
}
public int cal(int num1,int num2,String c){
int result=0;
switch (c){
case "+":result=num1+num2;break;
case "-":result=num1-num2;break;
case "×":result=num1*num2;break;
case "/":result=num1/num2;break;
}
return result;
}
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| public class ALTest {
public static void main(String[] args) {
String str = "12+((21+3)×4)-5";
List<String> postPrefixList = inPrefix2postPrefix(str);
System.out.println(postPrefixList);
int result = calbyPostPrefix(postPrefixList);
System.out.println(result);
}
public static int calbyPostPrefix(List<String> postPrefixList){
Stack<Integer> stack = new Stack<>();
for(String item:postPrefixList){
if(item.equals("+") || item.equals("-") || item.equals("×") || item.equals("/")){
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(cal(num1,num2,item));
}else{
stack.push(Integer.parseInt(item));
}
}
return stack.peek();
}
public static int cal(int num1,int num2,String c){
int result=0;
switch (c){
case "+":result=num1+num2;break;
case "-":result=num1-num2;break;
case "×":result=num1*num2;break;
case "/":result=num1/num2;break;
}
return result;
}
public static int getPriority(char c){
int priority=0;
switch (c){
case '+':priority=1;break;
case '-':priority=1;break;
case '×':priority=2;break;
case '/':priority=2;break;
}
return priority;
}
public static List<String> inPrefix2postPrefix(String str){
List<String> resultList = new ArrayList<>();
Stack<Character> opStack = new Stack<>();
int index=0;
while (index< str.length()){
char c = str.charAt(index);
if(c>='0' && c<='9'){
StringBuilder sb = new StringBuilder();
while (index<str.length() && (str.charAt(index)>='0' && str.charAt(index)<='9')){
sb.append(str.charAt(index));
index+=1;
}
resultList.add(sb.toString());
}else{
if(c=='(' || opStack.isEmpty()){
opStack.push(c);
} else if (c==')') {
while (!(opStack.peek()=='(')){
resultList.add(opStack.pop()+"");
}
opStack.pop();
} else if(opStack.peek()=='('){
opStack.push(c);
}else if(getPriority(opStack.peek())<getPriority(c)){
opStack.push(c);
}else{
while (getPriority(c)<=getPriority(opStack.peek())){
resultList.add(opStack.pop()+"");
if(opStack.size()==0 || opStack.peek()=='(') break;
}
opStack.push(c);
}
index+=1;
}
}
while (!opStack.isEmpty()){
resultList.add(opStack.pop()+"");
}
return resultList;
}
}
|
微信
支付宝