- 浏览: 2329 次
- 性别:
- 来自: 上海
文章分类
最新评论
对四则运算表达式字符串进行解析后计算出结果,可以使用逆波兰表达式进行处理。
首先说明一下什是逆波兰表达式:
逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家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
相关推荐
使用逆波兰表达式实现的四则运算解析库、计算器
使用C++模拟了计算器的四则运算,包括加减乘除以及括号优先级运算,主要解决办法是将键盘输入的四则运算表达式转为逆波兰表达式,然后再进一步计算逆波兰表达式的值,具体算法思路在主页,资源包括一个main.cpp文件...
通过把输入的中缀表达示转换为逆波兰式实现整数及小数的四则运算,为了简便,这个程序只支持小括号,中括号和大括号暂不支持,需要的话自己插入几句代码就行了。 gcc下编译通过,没在window下测试。
源代码 博文链接:https://leon-a.iteye.com/blog/186104
这是我用java写的一个计算器,除简单的四则运算外还可以计算小数,负数,可以有优先级判断。
1、四则运算 + - * / 、括弧()、正负(+ -) 2、百分数 %、求幂 ^ 、整数阶乘 ! (1 至 150) 3、参数符号计算,示例:a+b @@a=1,b=2 结算结果为3 用@@表示表达式中定义符号的值 4、常数e、圆周率PI 5、丰富的函数...
计算器的实现 算法题 逆波兰表达式实现优先级判断
带抽屉滑动效果,使用ViewPager滑动页面,使用逆波兰式对表达式进行计算,支持四则运算.rar,太多无法一一验证是否可用,程序如果跑不起来需要自调,部分代码功能进行参考学习。
用逆波兰(后缀表示)实现四则运算,从文件随机读取题目,对该次成绩进行存储并与上次成绩进行比较给出评语,提供用户接口,用户可自己添加题目到题库中。
java简易计算器,能够进行四则运算、三角函数运算,已实现优先级。 将中缀表达式转化成后缀表达式(逆波兰表达式) 主要运用了栈、简单的数学知识,java图形界面设计等相关知识
主要介绍了javascript中解析四则运算表达式的算法和示例,本文介绍了中缀表示法、逆波兰表示法这2种算法,并分别给出了代码实例,需要的朋友可以参考下
代码中包含通过逆波兰式php实现的计算四则运算表达式的方法,比如计算(103*(12/321+7)+3)*45的结果,网上常用的四则运算函数或者不能支持多位运算,或者不能支持括号,或者只有逆波兰式的实现。
按逆波兰表达式建立树 输出表达式树的各种遍历的结果。 打印表达式树。 删除表达式树。
1. a*b+c*(d+e) 逆波兰表达式: ab*cde+*+ 2. -a+-b*+c 逆波兰表达式: a~b~c@*+ 3.a-(-(b-c)) 逆波兰表达式: abc-~ - 预处理: -(负号)处理:用~代替 +(正号)处理:用@代替,或者将其在字符串中...
带抽屉滑动效果,使用ViewPager滑动页面,使用逆波兰式对表达式进行计算,支持四则运算
表达式计算器 采用堆債转换后缀表达式的计算方法 win API ,C++编写 vs2010工程