好玩的数据结构与算法——逆波兰表达式实现计算器求值

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

30

逆波兰表达式又叫后缀表达式,逆波兰表达式实现计算器求值,首先要把中缀表达式变成后缀表达式。先介绍一下前缀、中缀、后缀表达式。

一、前、中、后缀表达式

1.中缀表达式

中缀表达式就是我们常见的数学表达式,如:(3+40*6)*5-5
中缀表达式是我们人所熟悉的,人很容易就计算出来了,但是计算机不能够直接考虑到算数运算符的优先级关系,使用中缀表达式可能实现简单的计算工作(可参考这篇文章利用栈实现简单的计算器(加减乘除)),但是一旦涉及到了括号,计算机就不能够识别出优先级了。为了解决这个问题,研究人员就研究出了后缀表达式,后缀表达式能够使得计算机更简单的计算结果。

2.前缀表达式(波兰表达式)

前缀表达式又叫波兰表达式,前缀表达式的运算符位于操作数之前。
例如:

(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

中缀表达式转前缀表达式

  1. 构造两个栈,s1,s2分别存储运算符与操作数
  2. 从右至左扫描中缀表达式
    (1). 如果当前值为数值,读取,直到遇到运算符,将其转为一个数值并存入s2
    (2). 如果是运算符,则比较优先级
    a. 如果当前运算符的优先级大于等于s1栈顶运算符的优先级或s1栈空,则将运算符直接入栈;
    b.否则将栈顶运算符出栈并输出,直到当前运算符的优先级大于等于栈顶运算符的优先级,再将当前运算符入栈。
    (3).如果是括号,则根据括号的方向进行处理。如果是右括号,则直接入栈;否则,遇左括号前将所有的运算符全部出栈并输出,遇右括号后将左右的两括号一起删除。
  3. 重复上述操作2直至扫描结束,将栈内剩余运算符全部出栈并输出,再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。

3.后缀表达式(逆波兰表达式)

后缀表达式又叫逆波兰表达式,运算符位于操作数之后。
如:(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
再如:

中缀表达式转后缀表达式

  1. 初始化两个栈:运算符栈s1和储存中间结果的栈s2;
  2. 从左至右扫描中缀表达式;
  3. 遇到操作数时,将其压s2;
  4. 遇到运算符时,比较其与s1栈顶运算符的优先级:
    (1). 如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
    (2). 否则,若优先级比栈顶运算符的高,也将运算符压入s1;
    (3). 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较;
  5. 遇到括号时:
    (1) 如果是左括号“(”,则直接压入s1
    (2) 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
  6. 重复步骤2至5,直到表达式的最右边
  7. 将s1中剩余的运算符依次弹出并压入s2
  8. 依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

如:1+((2+3)*4)-5 转为后缀表达式的过程:

代码实现中缀表达式转后缀表达式:
先将中缀表达式转换成为对应的List,使用toInfixExpressionList方法,再见list转换为后缀表达式,使用parseSuffixExpression

private static final int ADD = 1; // +
private static final int SUB = 1; // -
private static final int MUL = 2; // *
private static final int DIV = 2; // //*** @Description: getLevelValue 获取运算符等级值*/
public static int getLevelValue(String operation){int res = 0;switch (operation){case "+":res = ADD;break;case "-":res = SUB;break;case "*":res = MUL;break;case "/":res = DIV;break;default:System.out.println(operation+"不是运算符");break;}return res;
}/*** @Description: toInfixExpressionList 将中缀表达式转换成对应的list*/
public static List<String> toInfixExpressionList(String s){ArrayList<String> stringArrayList = new ArrayList<>();int i = 0; // 指针,用于遍历中缀表达式的字符串String str;//多位数拼接char c;//每次遍历一个字符,存入cdo {c=s.charAt(i);if ((c < 48 || c >57) && c != '.' && c != ' '){  // 判断是不是运算符 ASCII 48~57对应数字0~9stringArrayList.add(""+c);i++;}else if(c == ' ') {i++;}else {str = ""; //重置strwhile ((i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) || c == '.'){str += c; //拼接i++;}stringArrayList.add(str);}}while (i < s.length());return stringArrayList;
}/*** @Description: parseSuffixExpression 转为后缀表达式*/
public static List<String> parseSuffixExpression(List<String> ls){Stack<String> s1 = new Stack<>(); // 符号栈// 说明: s2这个栈在整个转换过程中,灭有pop操作,后面需要逆序输出,比较麻烦,故使用List代替// Stack s2 = new Stack<>(); // 存储中间结果栈ArrayList<String> s2 = new ArrayList<>();for (String item : ls) {if (item.matches(NUMREGEX)){ //如果是一个数字s2.add(item);}else if (item.equals("(")){ //如果是左括号“(”,则直接压入s1s1.push(item);}else if (item.equals(")")){// 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃while (!s1.peek().equals("(")){s2.add(s1.pop());}s1.pop();  // 将小括号弹出s1,消除小括号}else {// 若item优先级小于等于栈顶运算符的优先级,将s1栈的栈顶运算符弹出压入s2,再次与s1中的新栈顶运算符比较while (s1.size() != 0 && getLevelValue(s1.peek()) >= getLevelValue(item)){s2.add(s1.pop());}// item优先级大于栈顶运算符,压入s1s1.push(item);}}// 将s1 剩下的运算符弹出并加入s2while (s1.size() != 0){s2.add(s1.pop());}// 因为我们使用了List替代了栈,故顺序就是对应的逆波兰表达式,不需要逆序return s2;
}

二、逆波兰表达式计算

后缀表达式求值原理:
从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:

  1. 从左至右扫描,将3和4压入堆栈;
  2. 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈;
  3. 将5入栈;
  4. 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
  5. 将6入栈;
  6. 最后是-运算符,计算出35-6的值,即29,由此得出最终结果

代码实现后缀表达式求值

/*** @Description: calculate 计算逆波兰表达式*/
public static double calculate(List<String> ls){Stack<Double> stack = new Stack<Double>();for (String item : ls) {if (item.matches(NUMREGEX)){// 入栈stack.push(Double.parseDouble(item));}else {// 注意出栈顺序double num2 = stack.pop();double num1 = stack.pop();double res = 0;if (item.equals("+")){res = num1 + num2;}else if (item.equals("-")){res = num1 - num2;}else if (item.equals("*")){res = num1 * num2;}else if (item.equals("/")){res = num1 / num2;}stack.push(res);}}return stack.pop(); // 返回结果
}

附逆波兰实现计算器完整代码:

public class PolandNotation {// 匹配数组public static final String NUMREGEX = "[1-9]\d*\.*\d*";private static final int ADD = 1; // +private static final int SUB = 1; // -private static final int MUL = 2; // *private static final int DIV = 2; // //*** @Description: getLevelValue 获取运算符等级值*/public static int getLevelValue(String operation){int res = 0;switch (operation){case "+":res = ADD;break;case "-":res = SUB;break;case "*":res = MUL;break;case "/":res = DIV;break;default:System.out.println(operation+"不是运算符");break;}return res;}public static void main(String[] args) {String expression = "1 +((2+3)*4)-5";List<String> infixExpressionList = toInfixExpressionList(expression);System.out.println("strings.toString() = " + infixExpressionList.toString());List<String> suffixExpression = parseSuffixExpression(infixExpressionList);System.out.println("suffixExpression = " + suffixExpression);double calculate = calculate(suffixExpression);System.out.println("calculate = " + calculate);}/*** @Description: toInfixExpressionList 将中缀表达式转换成对应的list*/public static List<String> toInfixExpressionList(String s){ArrayList<String> stringArrayList = new ArrayList<>();int i = 0; // 指针,用于遍历中缀表达式的字符串String str;//多位数拼接char c;//每次遍历一个字符,存入cdo {c=s.charAt(i);if ((c < 48 || c >57) && c != '.' && c != ' '){  // 判断是不是运算符 ASCII 48~57对应数字0~9stringArrayList.add(""+c);i++;}else if(c == ' ') {i++;}else {str = ""; //重置strwhile ((i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) || c == '.'){str += c; //拼接i++;}stringArrayList.add(str);}}while (i < s.length());return stringArrayList;}/*** @Description: parseSuffixExpression 转为后缀表达式*/public static List<String> parseSuffixExpression(List<String> ls){Stack<String> s1 = new Stack<>(); // 符号栈// 说明: s2这个栈在整个转换过程中,灭有pop操作,后面需要逆序输出,比较麻烦,故使用List代替// Stack s2 = new Stack<>(); // 存储中间结果栈ArrayList<String> s2 = new ArrayList<>();for (String item : ls) {if (item.matches(NUMREGEX)){ //如果是一个数字s2.add(item);}else if (item.equals("(")){ //如果是左括号“(”,则直接压入s1s1.push(item);}else if (item.equals(")")){// 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃while (!s1.peek().equals("(")){s2.add(s1.pop());}s1.pop();  // 将小括号弹出s1,消除小括号}else {// 若item优先级小于等于栈顶运算符的优先级,将s1栈的栈顶运算符弹出压入s2,再次与s1中的新栈顶运算符比较while (s1.size() != 0 && getLevelValue(s1.peek()) >= getLevelValue(item)){s2.add(s1.pop());}// item优先级大于栈顶运算符,压入s1s1.push(item);}}// 将s1 剩下的运算符弹出并加入s2while (s1.size() != 0){s2.add(s1.pop());}// 因为我们使用了List替代了栈,故顺序就是对应的逆波兰表达式,不需要逆序return s2;}/*** @Description: calculate 计算逆波兰表达式*/public static double calculate(List<String> ls){Stack<Double> stack = new Stack<Double>();for (String item : ls) {if (item.matches(NUMREGEX)){// 入栈stack.push(Double.parseDouble(item));}else {// 注意出栈顺序double num2 = stack.pop();double num1 = stack.pop();double res = 0;if (item.equals("+")){res = num1 + num2;}else if (item.equals("-")){res = num1 - num2;}else if (item.equals("*")){res = num1 * num2;}else if (item.equals("/")){res = num1 / num2;}stack.push(res);}}return stack.pop(); // 返回结果}}