本文实例讲述了java实现任意四则运算表达式求值算法。分享给大家供大家参考。具体分析如下：
该程序用于计算任意四则运算表达式。如 4 * ( 10 + 2 ) + 1 的结果应该为 49。
算法说明：
1. 首先定义运算符优先级。我们用一个
|
1
|
Map<String, Map<String, String>> |
来保存优先级表。这样我们就可以通过下面的方式来计算两个运算符的优先级了：
|
1
2
3
4
5
6
7
8
9
|
/** * 查表得到op1和op2的优先级 * @param op1 运算符1 * @param op2 运算符2 * @return ">", "<" 或 "=" */public String priority(String op1, String op2) { return priorityMap.get(op1).get(op2);} |
2. 扫描表达式字符串，每次读入一个 token 进行处理。
使用两个辅助栈：optStack用于保存运算符，numStack用于保存操作数. 我们用 '#' 作为表达式的起始和结果标志符。
读入一个token，如果它是数字，则压入numStack栈中；
如果它是运算符，则取出optStack栈的栈顶元素A，将 A 与 token 进行优先级比较。
如果 A < token，则将 token 压入optStack栈。
如果 A = token，则说明 token和A是一对括号，此时将optStack栈的栈顶元素弹出。
如果 A > token，则从numStack中弹出２个操作数，从optStack中弹出1个运算符，并计算结果。
当optStrack栈为空时（即栈顶元素为 '#'），numStack栈的栈顶元素即为表达式的值。
算法实现：
|
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
/** * 算术表达式求值。 * 3 + 4 * 12 结果为51 * @author whf * */public class EvaluateExpression { // 运算符优先级关系表 private Map<String, Map<String, String>> priorityMap = new HashMap<String, Map<String, String>>(); private LinkedStack<String> optStack = new LinkedStack<String>(); // 运算符栈 private LinkedStack<Double> numStack = new LinkedStack<Double>(); // 操作数栈 /** * 计算表达式 * @param exp 四则运算表达式, 每个符号必须以空格分隔 * @return */ public double calcualte(String exp) { StringTokenizer st = new StringTokenizer(exp); while (st.hasMoreTokens()) { String token = st.nextToken(); process(token); } return numStack.pop(); } /** * 读入一个符号串。 * 如果是数字，则压入numStack * 如果是运算符，则将optStack栈顶元素与该运算符进行优先级比较 * 如果栈顶元素优先级低，则将运算符压入optStack栈,如果相同，则弹出左括号，如果高，则取出２个数字，取出一个运算符执行计算，然后将结果压入numStack栈中 * @param token */ private void process(String token) { while (false == "#".equals(optStack.getTop()) || false == token.equals("#")) { // token is numeric if (true == isNumber(token)) { numStack.push(Double.parseDouble(token)); break; // token is operator } else { String priority = priority(optStack.getTop(), token); if ("<".equals(priority)) { optStack.push(token); break; } else if ("=".equals(priority)) { optStack.pop(); break; } else { double res = calculate(optStack.pop(), numStack.pop(), numStack.pop()); numStack.push(res); } } } } /** * 执行四则运算 * @param opt * @param n1 * @param n2 * @return */ private double calculate(String opt, double n1, double n2) { if ("+".equals(opt)) { return n2 + n1; } else if ("-".equals(opt)) { return n2 - n1; } else if ("*".equals(opt)) { return n2 * n1; } else if ("/".equals(opt)) { return n2 / n1; } else { throw new RuntimeException("unsupported operator:" + opt); } } /** * 检查一个String是否为数字 * @param token * @return */ private boolean isNumber(String token) { int LEN = token.length(); for (int ix = 0 ; ix < LEN ; ++ix) { char ch = token.charAt(ix); // 跳过小数点 if (ch == '.') { continue; } if (false == isNumber(ch)) { return false; } } return true; } /** * 检查一个字符是否为数字 * @param ch * @return */ private boolean isNumber(char ch) { if (ch >= '0' && ch <= '9') { return true; } return false; } /** * 查表得到op1和op2的优先级 * @param op1 运算符1 * @param op2 运算符2 * @return ">", "<" 或 "=" */ public String priority(String op1, String op2) { return priorityMap.get(op1).get(op2); } /** * 构造方法，初始化优先级表 */ public EvaluateExpression() { // initialize stack optStack.push("#"); // initialize priority table // + Map<String, String> subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("+", subMap); // - subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("-", subMap); // * subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("*", subMap); // / subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("/", subMap); // ( subMap = new HashMap<String, String>(); subMap.put("+", "<"); subMap.put("-", "<"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", "="); //subMap.put("#", ">"); priorityMap.put("(", subMap); // ) subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); //subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put(")", subMap); // # subMap = new HashMap<String, String>(); subMap.put("+", "<"); subMap.put("-", "<"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); //subMap.put(")", ">"); subMap.put("#", "="); priorityMap.put("#", subMap); }} |
程序测试：
|
1
2
3
|
String exp = "4 * ( 10 + 2 ) + 1 #";EvaluateExpression ee = new EvaluateExpression();out.println(ee.calcualte(exp)); |
运行结果为 49。
希望本文所述对大家的C++程序设计有所帮助。
