-
中缀表达式是人熟悉的表达式。例如 3 + 5 * 6
-
前缀表达式，也称波兰表达式，运算符写在操作数前面。例如 (3 + 4) * 5 - 6 对应的前缀表达式为：- * + 3 4 5 6
-
后缀表达式，也称逆波兰表达式，运算符写在操作数后面。例如 (3 + 4) * 5 - 6 对应的后缀表达式为：3 4 + 5 * 6 -
前缀表达式
求值规则：自右向左 扫描表达式，遇到数字时压栈，遇到运算符则弹出栈顶两个数做对应运算，并将结果压入栈中。
-
中缀表达式：( 3 + 4 ) * 5 - 6
-
前缀表达式：- * + 3 4 5 6
执行计算过程：
1. 将表达式 自右向左 扫描，将 6 5 4 3 依次压入栈中
2. 遇到 + 时，将 3 、4 弹出，计算 3 + 4，然后将结果 7 压入栈中
3. 遇到 * 时，将 7、5 弹出，计算 7 * 5，然后将结果 35 压入栈中
4. 遇到 - 时，将 35、6 弹出，计算 35 - 6，然后将结果 29 压入栈中
后缀表达式
求值规则：从左至右 依次扫描表达式，遇到数字压入栈中，遇到运算符则弹出栈顶两个数做对应运算，并将结果压入栈中。
-
中缀表达式：( 3 + 4 ) * 5 - 6
-
后缀表达式：3 4 + 5 * 6 -
执行计算过程：
1. 将表达式 从左至右 扫描，遇到括号，优先级最大，将3 4压入栈中
2. 再括号收尾后，遇到 + 时，将 4、3 弹出，计算 3 + 4，然后将结果 7 压入栈中
3. 将 5 压入栈中，左边为栈
4. 遇到 * 时，将 5、7 弹出，计算 7 * 5，然后将结果 35 压入栈中
5. 将 6 压入栈中
6. 遇到 - 时，将 35、6 弹出，计算 35 - 6，然后将结果 29 压入栈中
中缀表达式
需要把 中缀表达式转后缀表达式，再做计算
转化规则：把每个运算符都移到它的两个操作数的后面，然后删除括号即可。
下面表以 2 * ( ( 5 - 3 ) * 4 ) - 16 / 2 作为样例演示转换的步骤。
创建两个栈 a 和 b，a 用于存储转换过程，b 用于临时存储操作符与小括号。
| 运算步骤 |
扫描到字符 |
a 栈（栈低 -> 栈顶） |
b 栈（栈底 -> 栈顶） |
说明 |
| 1 |
2 |
2 |
^ |
数字直接压入 a |
| 2 |
* |
2 |
* |
b 中无符号，直接将 * 压入 b |
| 3 |
( |
2 |
*、( |
括号优先级最高，左括号直接压入 b |
| 4 |
( |
2 |
*、( 、( |
括号优先级最高，左括号直接压入 b |
| 5 |
5 |
2、5 |
*、( 、( |
数字直接压入 a |
| 6 |
- |
2、5 |
*、( 、( 、- |
- 优先级低于 (，由于 ( 不是运算符，- 压入 b |
| 7 |
3 |
2、5、3 |
*、( 、( 、- |
数字直接压入 a |
| 8 |
) |
2、5、3、- |
*、( |
遇到右括号，符号依次弹出 b，并依次压入 a，直至遇到左括号，且删除左括号 |
| 9 |
* |
2、5、3、- |
、( 、 |
* 比左括号优先级低，由于 ( 不是运算符，* 压入 b |
| 10 |
4 |
2、5、3、-、4 |
、( 、 |
数字直接压入 a |
| 11 |
) |
2、5、3、-、4、* |
* |
遇到右括号)，符号依次弹出 b，并依次压入 a，直至遇到左括号 (，且删除左括号 ( |
| 12 |
- |
2、5、3、-、4、、 |
- |
- 优先级低于 *，* 出栈并压入 a，此时 ( 变为栈顶元素，- 优先级低于 (，将 - 压入 b， |
| 13 |
16 |
2、5、3、-、4、、、16 |
- |
数字直接压入 a |
| 14 |
/ |
2、5、3、-、4、、、16 |
-、/ |
/ 优先级高于 -，/ 压入 b |
| 15 |
2 |
2、5、3、-、4、、、16、2 |
-、/ |
数字直接压入 a |
| 16 |
^ |
2、5、3、-、4、、、16、2、/ |
- |
遍历完成，将 b 中的元素依次压入 a |
| 17 |
^ |
2、5、3、-、4、、、16、2、/、- |
^ |
遍历完成，将 b 中的元素依次压入 a |
-
每次扫描到的 数字 直接压入 a 栈
-
每次扫描到的符号 x 需要与 b 栈顶部的符号 y 比较优先级，如果 x > y，则 x 压入 b 栈，如果 x <= y，将 b 栈顶元素弹出后压入 a，继续比较 x 与 下一个 y。
-
最终获取的表达式为：2 5 3 - 4 * * 16 2 / -，需要将 a 中的元素弹出后再逆序。
中缀表达式求值（整数版）
通过栈的特性，转换为后缀表达式后求值
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
public class ExpressionEvaluation {
final static List<Character> symbol = Arrays.asList('+', '-', '*', '/', '(', ')');
public static void main(String[] args) {
List<String> list = parse("400+5 * 4 / (12-7)");
System.out.println(list.toString());
List<String> list2 = infixConvertToPostfix(list);
System.out.println(list2.toString());
System.out.println(compute(list2));
}
public static List<String> parse(String expre) {
StringBuilder num = new StringBuilder();
List<String> list = new ArrayList<>();
char charVal;
for (int i = 0; i < expre.length(); i++) {
charVal = expre.charAt(i);
if (isNumber(charVal)) {
num.append(charVal);
} else if (symbol.contains(charVal)) {
if (num.length() > 0) {
list.add(num.toString());
}
num = new StringBuilder();
list.add(String.valueOf(charVal));
}
}
if (num.length() > 0) {
list.add(num.toString());
}
return list;
}
public static List<String> infixConvertToPostfix(List<String> list) {
Stack<String> s1 = new Stack<>();
List<String> s2 = new ArrayList<>();
for (String s : list) {
if (s.matches("\\d+")) {
s2.add(s);
} else if ("(".equals(s)) {
s1.push(s);
} else if (")".equals(s)) {
while (!"(".equals(s1.peek())) {
s2.add(s1.pop());
}
s1.pop();
} else {
while (!s1.empty() && (getPriority(s) <= getPriority(s1.peek()))) {
s2.add(s1.pop());
}
s1.push(s);
}
}
while (!s1.empty()) {
s2.add(s1.pop());
}
return s2;
}
public static int compute(List<String> list) {
Stack<Integer> num = new Stack<>();
int num1 = 0;
int num2 = 0;
int res = 0;
for (String s : list) {
if (s.matches("\\d+")) {
num.push(Integer.parseInt(s));
} else {
num1 = num.pop();
num2 = num.pop();
switch (s) {
case "+":
res = num2 + num1;
break;
case "-":
res = num2 - num1;
break;
case "*":
res = num2 * num1;
break;
case "/":
res = num2 / num1;
break;
default:
throw new RuntimeException("扫描到未知符号！");
}
num.push(res);
}
}
return num.pop();
}
public static boolean isNumber(char c) {
return 48 <= c && c <= 57;
}
public static int getPriority(String s) {
if ("*".equals(s) || "/".equals(s)) {
return 2;
}
if ("+".equals(s) || "-".equals(s)) {
return 1;
}
if ("(".equals(s)) {
return 0;
}
throw new RuntimeException("扫描到未知符号！");
}
}
|
