snoics
- 浏览: 2386 次
- 性别:
- 来自: 上海
-
文章分类
最新评论
对四则运算表达式字符串进行解析后计算出结果，可以使用逆波兰表达式进行处理。
首先说明一下什是逆波兰表达式：
逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。
将一个普通的中序表达式转换为逆波兰表达式的一般算法是：
(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。
(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。
(4)如果不是数字，该字符则是运算符，此时需比较优先关系。
做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。
(5)重复上述操作(3)-(4)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。
以上内容来源百度
下面进入正题，按照以上的算法说明自己实现四则运算如下：
1 package com.snoics.jdk.arithmetic;
2
3 import java.math.BigDecimal;
4 import java.math.RoundingMode;
5 import java.util.ArrayList;
6 import java.util.LinkedList;
7 import java.util.List;
8
9 /**
10 *
11 * 通过四则运算表达式字符串，构造逆波兰表达式，计算结果
12 *
13 * (1)从左至右扫描该算术表达式，从第一个字符开始判断，
14 * 如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。
15 *
16 * (2)如果不是数字，该字符则是运算符，此时需比较优先关系。
17 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。
18 如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。
19 倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级
20 低于当前运算符，将该字符入栈。
21
22 (3)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，
23 我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。
24 *
25 * @author:shiwei
26 *
27 *
28 */
29 public class Arithmetic {
30
31 /**
32 * +
33 */
34 private final static String OP1 = "+";
35
36 /**
37 * -
38 */
39 private final static String OP2 = "-";
40
41 /**
42 * *
43 */
44 private final static String OP3 = "*";
45
46 /**
47 * /
48 */
49 private final static String OP4 = "/";
50
51 /**
52 * (
53 */
54 private final static String OPSTART = "(";
55
56 /**
57 * )
58 */
59 private final static String OPEND = ")";
60
61 //四则运算式
62 private String exp;
63
64 //精确到小数点后几位
65 private int precision=2;
66
67 //取舍模式
68 private RoundingMode roundingMode=RoundingMode.HALF_UP;
69
70 //四则运算解析
71 private List<String> expList = new ArrayList<String>();
72
73 //存放逆波兰表达式
74 private List<String> rpnList = new ArrayList<String>();
75
76 /**
77 * 四则运算
78 * @param exp 四则运算表达式
79 * @param precision 精确到小数点后几位
80 * @param roundingMode 取舍模式
81 */
82 public Arithmetic(String exp,int precision,RoundingMode roundingMode) {
83 this.exp = exp;
84 this.precision=precision;
85 this.roundingMode=roundingMode;
86
87 parse();
88 createRPN();
89 }
90
91 /**
92 * 分析四则运算表达式，将数字与运算符进行分解
93 */
94 private void parse() {
95 int length = exp.length();
96
97 String tempStr = "";
98 for (int i = 0; i < length; i++) {
99 String tempChar = exp.substring(i, i + 1);
100 if (isNumber(tempChar)) {
101 tempStr += tempChar;
102 } else {
103 if (!tempStr.equals("")) {
104 expList.add(tempStr);
105 }
106 expList.add(tempChar);
107 tempStr = "";
108 }
109 }
110 if (!tempStr.equals("")) {
111 expList.add(tempStr);
112 }
113
114 }
115
116 /**
117 * 判断当前字符或字符串是否是数字
118 * @param str
119 * @return
120 */
121 private boolean isNumber(String str) {
122 return str.startsWith("0")
123 || str.startsWith("1")
124 || str.startsWith("2")
125 || str.startsWith("3")
126 || str.startsWith("4")
127 || str.startsWith("5")
128 || str.startsWith("6")
129 || str.startsWith("7")
130 || str.startsWith("8")
131 || str.startsWith("9")
132 || str.startsWith(".");
133
134 }
135
136 /**
137 * 判断当前字符是否是 (
138 * @param str
139 * @return
140 */
141 private boolean isParenthesesStart(String str) {
142 return str.equals(OPSTART);
143 }
144
145 /**
146 * 判断当前字符是否是 )
147 * @param str
148 * @return
149 */
150 private boolean isParenthesesEnd(String str) {
151 return str.equals(OPEND);
152 }
153
154 /**
155 * 判断当前字符是否是高优先级运算符 * /
156 * @param str
157 * @return
158 */
159 private boolean isHeighOperator(String str) {
160 if (str.equals(OP3)
161 || str.equals(OP4)) {
162 return true;
163 } else {
164 return false;
165 }
166 }
167
168 /**
169 * 对比两个字符串的优先级
170 * @param str1
171 * @param str2
172 * @return
173 */
174 private boolean compare(String str1, String str2) {
175 if (str1.equals(OPSTART)) {
176 return false;
177 }
178 if (isHeighOperator(str2)) {
179 return false;
180 } else {
181 if (isHeighOperator(str1)) {
182 return true;
183 } else {
184 return false;
185 }
186 }
187 }
188
189 /**
190 * 将分解后的四则运算列表构建成逆波兰表达式列表
191 */
192 private void createRPN() {
193 Stack stack = new Stack();
194
195 int length = expList.size();
196 for (int i = 0; i < length; i++) {
197 String c = expList.get(i);
198
199 //如果是数字，直接放到逆波兰链表的最后
200 if (isNumber(c)) {
201 rpnList.add(c);
202 } else {
203 //如果不是数字
204
205 //如果是左括号，则直接将左括号压入栈
206 if (isParenthesesStart(c)) {
207 stack.push(c);
208 } else if (isParenthesesEnd(c)) {
209 //如果是右括号
210
211 //进行出栈操作，直到栈为空或者遇到第一个左括号
212 while (!stack.isEmpty()) {
213 //将栈顶字符串做出栈操作
214 String tempC = stack.pop();
215 if (!tempC.equals(OPSTART)) {
216 //如果不是左括号，则将字符串直接放到逆波兰链表的最后
217 rpnList.add(tempC);
218 }else{
219 //如果是左括号，退出循环操作
220 break;
221 }
222 }
223 } else {
224 //如果栈内为空
225 if (stack.isEmpty()) {
226 //将当前字符串直接压栈
227 stack.push(c);
228 } else {
229 //如果栈不为空
230
231 //比较栈顶字符串与当前字符串的优先级，
232 if (compare(stack.top(), c)) {
233 //如果栈顶元素的优先级大于当前字符串,则进行出栈操作
234 //将栈顶元素直接放到逆波兰链表的最后
235 //直到栈内为空，或者当前元素的优先级不小于栈顶元素优先级
236 while (!stack.isEmpty() && compare(stack.top(), c)) {
237 rpnList.add(stack.pop());
238 }
239 }
240 //将当前字符串直接压栈
241 stack.push(c);
242 }
243 }
244
245 }
246 }
247
248 //如果栈不为空，则将栈中所有元素出栈放到逆波兰链表的最后
249 while (!stack.isEmpty()) {
250 rpnList.add(stack.pop());
251 }
252 }
253
254 /**
255 * 通过逆波兰表达式计算结果
256 * @return
257 */
258 public String calculate(){
259 Stack numberStack = new Stack();
260
261 int length=rpnList.size();
262 for(int i=0;i<length;i++){
263 String temp=rpnList.get(i);
264 if(isNumber(temp)){
265 numberStack.push(temp);
266 }else{
267 BigDecimal tempNumber1 = getBigDecimal(numberStack.pop(),
268 precision,
269 roundingMode);
270
271 BigDecimal tempNumber2 = getBigDecimal(numberStack.pop(),
272 precision,
273 roundingMode);
274
275 BigDecimal tempNumber = getBigDecimal("",
276 precision,
277 roundingMode);
278
279 if(temp.equals(OP1)){
280 tempNumber=tempNumber2.add(tempNumber1);
281 }else if(temp.equals(OP2)){
282 tempNumber=tempNumber2.subtract(tempNumber1);
283 }else if(temp.equals(OP3)){
284 tempNumber=tempNumber2.multiply(tempNumber1);
285 }else if(temp.equals(OP4)){
286 tempNumber=tempNumber2.divide(tempNumber1,
287 precision,
288 roundingMode);
289 }
290
291 numberStack.push(tempNumber.toString());
292
293 }
294 }
295
296 return numberStack.pop();
297 }
298
299 /**
300 * 获取逆波兰表达式字符串
301 * @return
302 */
303 public String getRPN(){
304
305 String rpn="";
306
307 int rpnLength=rpnList.size();
308 for(int i=0;i<rpnLength;i++){
309 rpn+=rpnList.get(i)+" ";
310 }
311
312 return rpn;
313 }
314
315 /**
316 * 按精确度计算结果
317 * @param numString
318 * @param precision
319 * @param roundingMode
320 * @return
321 */
322 public static BigDecimal getBigDecimal(String numString,
323 int precision,
324 RoundingMode roundingMode){
325 String precisionFlag="0";
326 if(numString==null || numString.equals("")){
327 precisionFlag="0.00";
328 }else{
329 precisionFlag=numString;
330 }
331 BigDecimal bigDecimal = new BigDecimal(precisionFlag);
332 bigDecimal.setScale(precision,roundingMode);
333 return bigDecimal;
334 }
335
336 /**
337 * 栈
338 *
339 *
340 * @author shiwei
341 *
342 */
343 private class Stack {
344
345 LinkedList<String> stackList = new LinkedList<String>();
346
347 public Stack() {
348
349 }
350
351 /**
352 * 入栈
353 * @param expression
354 */
355 public void push(String expression) {
356 stackList.addLast(expression);
357 }
358
359 /**
360 * 出栈
361 * @return
362 */
363 public String pop() {
364 return stackList.removeLast();
365 }
366
367 /**
368 * 栈顶元素
369 * @return
370 */
371 public String top() {
372 return stackList.getLast();
373 }
374
375 /**
376 * 栈是否为空
377 * @return
378 */
379 public boolean isEmpty() {
380 return stackList.isEmpty();
381 }
382 }
383
384 public static void main(String[] args) {
385
386 String str = "1+(2+3)*(100-5*(9+8))/2.3+6-19";
387
388
389
390
391 System.out.println("====================================");
392
393 //将四则运算字符串分解为逆波兰表达式后计算结果
394 Arithmetic arithmetic=new Arithmetic(str,10,RoundingMode.HALF_UP);
395 String rpn=arithmetic.getRPN();
396 System.out.println("逆波兰表达式 : "+rpn);
397 System.out.println("计算结果 : "+arithmetic.calculate());
398 }
399
400 }
401
最后的运行计算结果如下：
====================================
逆波兰表达式 : 1 2 3 + 100 5 9 8 + * - 2.3 / * 6 19 - + +
计算结果 : 20.6086956520
0
顶
顶
0
踩
踩
分享到：
发表评论
相关推荐
本项目是一个基于JavaScript开发的逆波兰表达式解析库，用于实现四则运算的计算器。 在逆波兰表达式中，一个表达式如 "2 + 3 * 4" 将被转换为 "2 3 4 *" 的序列，这样计算器只需依次读取数字和操作符，遇到操作符时...
本项目提供的源代码（rpn-calculate-code）应该包含实现这些功能的详细代码，可以通过阅读和理解代码来深入学习逆波兰表达式和四则运算的解析机制。对于编程爱好者和学习者来说，这是一个很好的实践案例，可以帮助...
- 如果E1和E2是逆波兰表达式，则E1 E2 ω也是逆波兰表达式，其中ω是任一运算符。 2. **语法规则**： - 在逆波兰表达式中，操作数出现的顺序与中缀表达式中操作数出现的顺序相同。 - 运算符一律按照计算顺序从左...
使用C++模拟了计算器的四则运算，包括加减乘除以及括号优先级运算，主要解决办法是将键盘输入的四则运算表达式转为逆波兰表达式，然后再进一步计算逆波兰表达式的值，具体算法思路在主页，资源包括一个main.cpp文件...
使用逆波兰表达式实现的四则运算解析库、计算器（JavaScript） 功能 任意顺序的四则+-*/运算 支持() 前端后端通用 提供直接计算函数 提供四则运算表达式转逆波兰AST函数 提供语法分析函数(暂时只支持上下两个字符...
通过把输入的中缀表达示转换为逆波兰式实现整数及小数的四则运算，为了简便，这个程序只支持小括号，中括号和大括号暂不支持，需要的话自己插入几句代码就行了。 gcc下编译通过，没在window下测试。
其中，中缀表达式是我们通常使用的运算符在操作数之间的形式，如 "2 + 3 * 4"，而后缀表达式，也称为逆波兰表达式，是一种将运算符置于操作数之后的表示方式，例如 "2 3 4 *" 表示 "2 加上 3 乘以 4" 的结果。...
`Operate`函数实现了四则运算，根据传入的操作符执行相应的数学运算。值得注意的是，该函数还包含了错误处理，例如当除数为0时会抛出错误，防止运行时异常。 ### 逆波兰表达式求值流程 1. **初始化栈**：创建一个...
总之，逆波兰表达式算法提供了一种简洁、高效的方式来计算数学表达式，其核心在于使用栈数据结构和运算符优先级规则。在`ExpressionParserUtil.java`文件中，我们可以找到具体的实现细节，这为我们理解和扩展该算法...
#### 四、逆波兰表达式的实现 为了更好地理解逆波兰表达式的实现过程，我们可以参考以下伪代码： ```plaintext stack = new Stack() for each token in expression: if token is a number: stack.push(token) ...
3. **计算逆波兰表达式**：使用栈对逆波兰表达式进行求值。遍历表达式的每个元素，如果遇到数字直接入栈，如果是运算符，则取出栈顶的两个数进行相应运算，结果入栈，直至表达式结束，栈顶元素即为结果。 4. **检查...
在这个“MFC基于逆波兰算法的四则运算计算器”项目中，开发者使用C++和MFC构建了一个可以执行加、减、乘、除的计算器。逆波兰表达式的优势在于，它简化了表达式的解析过程，因为无需处理运算符的优先级和括号问题。...
评估逆波兰表达式则相对简单，同样使用栈，从左到右扫描后缀表达式，遇到数字就压入栈，遇到操作符则取出栈顶两个数进行运算，结果再压回栈。当表达式扫描完毕，栈中只剩一个元素，这个元素就是最终的结果。 在这个...
在数据结构的学习中，算术表达式的四则运算是一个重要的应用领域。这涉及到如何通过编程方式解析和计算涉及加、减、乘、除操作的数学表达式。在本项目中，我们将聚焦于如何处理输入的字符串形式的算术表达式，并通过...
逆波兰表达式是一种特殊的表达式形式，它的运算符位于运算对象的后面，而不是像传统的四则运算那样位于两个运算对象之间。例如，传统的中缀表达式"a+b"在逆波兰表达式中变成了"a b +"。 二、逆波兰表达式在Java中的...
计算器的实现 算法题 逆波兰表达式实现优先级判断