使用逆波兰表达式进行四则运算
对四则运算表达式字符串进行解析后计算出结果,可以使用逆波兰表达式进行处理。
首先说明一下什是逆波兰表达式:
下面进入正题,按照以上的算法说明自己实现四则运算如下:
最后的运行计算结果如下:
对四则运算表达式字符串进行解析后计算出结果,可以使用逆波兰表达式进行处理。
首先说明一下什是逆波兰表达式:
逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法,每一运算符都置于其运算对象之后,故称为后缀表示。 将一个普通的中序表达式转换为逆波兰表达式的一般算法是: (1)首先构造一个运算符栈,此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式,为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式,从第一个字符开始判断,如果该字符是数字,则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字,该字符则是运算符,此时需比较优先关系。 做法如下:将该字符与运算符栈顶的运算符的优先关系相比较。如果,该字符优先关系高于此运算符栈顶的运算符,则将该运算符入栈。倘若不是的话,则将栈顶的运算符从栈中弹出,直到栈顶运算符的优先级低于当前运算符,将该字符入栈。 (5)重复上述操作(3)-(4)直至扫描完整个简单算术表达式,确定所有字符都得到正确处理,我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。
下面进入正题,按照以上的算法说明自己实现四则运算如下:
package com.snoics.jdk.arithmetic; import java.math.BigDecimal; import java.math.RoundingMode; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; /** * * 通过四则运算表达式字符串,构造逆波兰表达式,计算结果 * * (1)从左至右扫描该算术表达式,从第一个字符开始判断, * 如果该字符是数字,则分析到该数字串的结束并将该数字串直接输出。 * * (2)如果不是数字,该字符则是运算符,此时需比较优先关系。 做法如下:将该字符与运算符栈顶的运算符的优先关系相比较。 如果,该字符优先关系高于此运算符栈顶的运算符,则将该运算符入栈。 倘若不是的话,则将栈顶的运算符从栈中弹出,直到栈顶运算符的优先级 低于当前运算符,将该字符入栈。 (3)重复上述操作(1)-(2)直至扫描完整个简单算术表达式,确定所有字符都得到正确处理, 我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 * * @author:shiwei * * */ public class Arithmetic { /** * + */ private final static String OP1 = "+"; /** * - */ private final static String OP2 = "-"; /** * * */ private final static String OP3 = "*"; /** * / */ private final static String OP4 = "/"; /** * ( */ private final static String OPSTART = "("; /** * ) */ private final static String OPEND = ")"; //四则运算式 private String exp; //精确到小数点后几位 private int precision=2; //取舍模式 private RoundingMode roundingMode=RoundingMode.HALF_UP; //四则运算解析 private List<String> expList = new ArrayList<String>(); //存放逆波兰表达式 private List<String> rpnList = new ArrayList<String>(); /** * 四则运算 * @param exp 四则运算表达式 * @param precision 精确到小数点后几位 * @param roundingMode 取舍模式 */ public Arithmetic(String exp,int precision,RoundingMode roundingMode) { this.exp = exp; this.precision=precision; this.roundingMode=roundingMode; parse(); createRPN(); } /** * 分析四则运算表达式,将数字与运算符进行分解 */ private void parse() { int length = exp.length(); String tempStr = ""; for (int i = 0; i < length; i++) { String tempChar = exp.substring(i, i + 1); if (isNumber(tempChar)) { tempStr += tempChar; } else { if (!tempStr.equals("")) { expList.add(tempStr); } expList.add(tempChar); tempStr = ""; } } if (!tempStr.equals("")) { expList.add(tempStr); } } /** * 判断当前字符或字符串是否是数字 * @param str * @return */ private boolean isNumber(String str) { return str.startsWith("0") || str.startsWith("1") || str.startsWith("2") || str.startsWith("3") || str.startsWith("4") || str.startsWith("5") || str.startsWith("6") || str.startsWith("7") || str.startsWith("8") || str.startsWith("9") || str.startsWith("."); } /** * 判断当前字符是否是 ( * @param str * @return */ private boolean isParenthesesStart(String str) { return str.equals(OPSTART); } /** * 判断当前字符是否是 ) * @param str * @return */ private boolean isParenthesesEnd(String str) { return str.equals(OPEND); } /** * 判断当前字符是否是高优先级运算符 * / * @param str * @return */ private boolean isHeighOperator(String str) { if (str.equals(OP3) || str.equals(OP4)) { return true; } else { return false; } } /** * 对比两个字符串的优先级 * @param str1 * @param str2 * @return */ private boolean compare(String str1, String str2) { if (str1.equals(OPSTART)) { return false; } if (isHeighOperator(str2)) { return false; } else { if (isHeighOperator(str1)) { return true; } else { return false; } } } /** * 将分解后的四则运算列表构建成逆波兰表达式列表 */ private void createRPN() { Stack stack = new Stack(); int length = expList.size(); for (int i = 0; i < length; i++) { String c = expList.get(i); //如果是数字,直接放到逆波兰链表的最后 if (isNumber(c)) { rpnList.add(c); } else { //如果不是数字 //如果是左括号,则直接将左括号压入栈 if (isParenthesesStart(c)) { stack.push(c); } else if (isParenthesesEnd(c)) { //如果是右括号 //进行出栈操作,直到栈为空或者遇到第一个左括号 while (!stack.isEmpty()) { //将栈顶字符串做出栈操作 String tempC = stack.pop(); if (!tempC.equals(OPSTART)) { //如果不是左括号,则将字符串直接放到逆波兰链表的最后 rpnList.add(tempC); }else{ //如果是左括号,退出循环操作 break; } } } else { //如果栈内为空 if (stack.isEmpty()) { //将当前字符串直接压栈 stack.push(c); } else { //如果栈不为空 //比较栈顶字符串与当前字符串的优先级, if (compare(stack.top(), c)) { //如果栈顶元素的优先级大于当前字符串,则进行出栈操作 //将栈顶元素直接放到逆波兰链表的最后 //直到栈内为空,或者当前元素的优先级不小于栈顶元素优先级 while (!stack.isEmpty() && compare(stack.top(), c)) { rpnList.add(stack.pop()); } } //将当前字符串直接压栈 stack.push(c); } } } } //如果栈不为空,则将栈中所有元素出栈放到逆波兰链表的最后 while (!stack.isEmpty()) { rpnList.add(stack.pop()); } } /** * 通过逆波兰表达式计算结果 * @return */ public String calculate(){ Stack numberStack = new Stack(); int length=rpnList.size(); for(int i=0;i<length;i++){ String temp=rpnList.get(i); if(isNumber(temp)){ numberStack.push(temp); }else{ BigDecimal tempNumber1 = getBigDecimal(numberStack.pop(), precision, roundingMode); BigDecimal tempNumber2 = getBigDecimal(numberStack.pop(), precision, roundingMode); BigDecimal tempNumber = getBigDecimal("", precision, roundingMode); if(temp.equals(OP1)){ tempNumber=tempNumber2.add(tempNumber1); }else if(temp.equals(OP2)){ tempNumber=tempNumber2.subtract(tempNumber1); }else if(temp.equals(OP3)){ tempNumber=tempNumber2.multiply(tempNumber1); }else if(temp.equals(OP4)){ tempNumber=tempNumber2.divide(tempNumber1, precision, roundingMode); } numberStack.push(tempNumber.toString()); } } return numberStack.pop(); } /** * 获取逆波兰表达式字符串 * @return */ public String getRPN(){ String rpn=""; int rpnLength=rpnList.size(); for(int i=0;i<rpnLength;i++){ rpn+=rpnList.get(i)+" "; } return rpn; } /** * 按精确度计算结果 * @param numString * @param precision * @param roundingMode * @return */ public static BigDecimal getBigDecimal(String numString, int precision, RoundingMode roundingMode){ String precisionFlag="0"; if(numString==null || numString.equals("")){ precisionFlag="0.00"; }else{ precisionFlag=numString; } BigDecimal bigDecimal = new BigDecimal(precisionFlag); bigDecimal.setScale(precision,roundingMode); return bigDecimal; } /** * 栈 * * * @author shiwei * */ private class Stack { LinkedList<String> stackList = new LinkedList<String>(); public Stack() { } /** * 入栈 * @param expression */ public void push(String expression) { stackList.addLast(expression); } /** * 出栈 * @return */ public String pop() { return stackList.removeLast(); } /** * 栈顶元素 * @return */ public String top() { return stackList.getLast(); } /** * 栈是否为空 * @return */ public boolean isEmpty() { return stackList.isEmpty(); } } public static void main(String[] args) { String str = "1+(2+3)*(100-5*(9+8))/2.3+6-19"; System.out.println("===================================="); //将四则运算字符串分解为逆波兰表达式后计算结果 Arithmetic arithmetic=new Arithmetic(str,10,RoundingMode.HALF_UP); String rpn=arithmetic.getRPN(); System.out.println("逆波兰表达式 : "+rpn); System.out.println("计算结果 : "+arithmetic.calculate()); } }
最后的运行计算结果如下:
==================================== 逆波兰表达式 : 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工程