逆波兰计算器

短命女 2022-12-02 10:52 185阅读 0赞

逆波兰表达式又叫做后缀表达式，逆波兰表达式把运算量写在前面,把运算符写在后面。

我们平时书写的表达式都是中缀表达式，这个表达式更加方便我们进行计算。但是相对于计算机而言，逆波兰表达式运算更加方便。只需要入栈和出栈两种操作就可以搞定所有运算，遇到操作数就入栈，遇到运算符就出栈，然后将栈顶的两个操作数进行相应运算。

所以，要想用代码实现计算器的首要步骤，就是将 中缀表达式 转为 后缀表达式。

中缀表达式转后缀表达式

步骤如下：

  1. 初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2；
  2. 从左至右扫描中缀表达式；
  3. 遇到操作数时，将其压 s2；

  4. 遇到运算符时，比较其与 s1 栈顶运算符的优先级：

    ①. 如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

    ②. 否则，若优先级比栈顶运算符的高，也将运算符压入 s1；

    ③. 否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到4.①与 s1 中新的栈顶运算符相比较；

  5. 遇到括号时：

    ①. 如果是左括号”(“，则直接压入 s1；

    ②. 如果是右括号”)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃；

  6. 重复步骤 2—5，直到扫描到表达式的最右边。
  7. 将 s1 中剩余的运算符依次弹出并压入 s2。
  8. 依次弹出 s2 中的元素并输出，结果的逆序即为 中缀表达式 对应的 后缀表达式。

形如：

中缀表达式“1+((2+3)×4)-5”，转为后缀表达式的结果是：

1 2 3 + 4 × + 5 –

代码实现

下面的代码只能进行整数的运算。

首先声明一个常量类，里面记录着运算符的字符。

  1. public class Constants { 
  3.     public static final String ADD_SYMBOL = "+";
  5.     public static final String SUB_SYMBOL = "-";
  7.     public static final String MUL_SYMBOL = "*";
  9.     public static final String DIV_SYMBOL = "/";
  10. }

接着创建一个返回运算符优先级的类。

  1. public class Operation { 
  3.     /** * 加 */
  4.     private static int ADD = 1;
  5.     /** * 减 */
  6.     private static int SUB = 1;
  7.     /** * 乘 */
  8.     private static int MUL = 2;
  9.     /** * 除 */
  10.     private static int DIV = 2;
  12.     /** * TODO 返回对应的优先级 */
  13.     public static int getValue(String operand) { 
  14.         int result = 0;
  15.         switch (operand) { 
  16.             case Constants.ADD_SYMBOL:
  17.                 result = ADD;
  18.                 break;
  19.             case Constants.SUB_SYMBOL:
  20.                 result = SUB;
  21.                 break;
  22.             case Constants.MUL_SYMBOL:
  23.                 result = MUL;
  24.                 break;
  25.             case Constants.DIV_SYMBOL:
  26.                 result = DIV;
  27.                 break;
  28.             default:
  29.                 System.out.println("不存在该运算符");
  30.                 break;
  31.         }
  32.         return result;
  33.     }
  34. }

最后就是核心功能了。编写中缀表达式转后缀表达式、计算。

  1. public class ReversePolandCalculator { 
  3.     /** * TODO 将中缀表达式转 list 集合 * * @param str * @return java.util.List<java.lang.String> */
  4.     public static List<String> infixExpressionToList(String str) { 
  5.         List<String> list = new ArrayList<>();
  6.         // 作为一个指针
  7.         int index = 0;
  8.         int zeroAscii = 48;
  9.         int nineAscii = 57;
  10.         // 如果这个操作数是多位数
  11.         StringBuilder mStr;
  12.         // 存放每一个字符
  13.         char ch;
  14.         do { 
  15.             // 如果 ch 是一个 非数字，需要加入到 list(0-9的ASCII值是48-57)
  16.             if ((ch = str.charAt(index)) < zeroAscii || (ch = str.charAt(index)) > nineAscii) { 
  17.                 list.add("" + ch);
  18.                 // 指针后移
  19.                 index++;
  20.             } else { 
  21.                 // 如果是一个数，需要考虑多位数
  22.                 mStr = new StringBuilder();
  23.                 while (index < str.length() && (ch = str.charAt(index)) >= zeroAscii && (ch = str.charAt(index)) <= nineAscii) { 
  24.                     mStr.append(ch);
  25.                     index++;
  26.                 }
  27.                 list.add(mStr.toString());
  28.             }
  29.         } while (index < str.length());
  30.         return list;
  31.     }
  33.     /** * TODO 将 中缀表达式的 List 集合转 后缀表达式 * * @param infixList * @return java.util.List<java.lang.String> */
  34.     public static List<String> infixToSuffixExpressionList(List<String> infixList) { 
  35.         // 符号栈
  36.         Stack<String> stack = new Stack<>();
  37.         // 存储中间结果的
  38.         List<String> resultList = new ArrayList<>();
  39.         String leftBracket = "(";
  40.         String rightBracket = ")";
  42.         // 遍历
  43.         for (String item : infixList) { 
  44.             // 如果是一个数，加入 resultList
  45.             if (item.matches("\\d+")) { 
  46.                 resultList.add(item);
  47.             } else if (item.equals(leftBracket)) { 
  48.                 stack.push(item);
  49.             } else if (item.equals(rightBracket)) { 
  50.                 // 如果是 右括号，则依次弹出 stack 栈顶的运算符，并压入 resultList，直到遇到左括号为止，此时将这一对括号丢弃
  51.                 while (!stack.peek().equals(leftBracket)) { 
  52.                     resultList.add(stack.pop());
  53.                 }
  54.                 // 将 ( 弹出 stack 栈，消除小括号
  55.                 stack.pop();
  56.             } else { 
  57.                 // 当 item 的优先级小于等于 stack栈顶运算符，将 stack 栈顶的运算符弹出并加入到 resultList 中，再次与 stack 中新的栈顶运算符相比较
  58.                 while (stack.size() != 0 && Operation.getValue(stack.peek()) >= Operation.getValue(item)) { 
  59.                     resultList.add(stack.pop());
  60.                 }
  61.                 // 将 此时 的 item压入栈
  62.                 stack.push(item);
  63.             }
  64.         }
  66.         // 将 stack 中剩余的运算符依次弹出并加入到 resultList
  67.         while (stack.size() != 0) { 
  68.             resultList.add(stack.pop());
  69.         }
  70.         // 因为 存放到 List中，因此按顺序输出就是 对应的 后缀表达式
  71.         return resultList;
  72.     }
  74.     /** * TODO 计算 * * @param expression * @return int */
  75.     public static int calculate(List<String> expressionList) { 
  76.         // 创建栈
  77.         Stack<String> stack = new Stack<>();
  78.         // 遍历
  79.         for (String item : expressionList) { 
  80.             // 使用正则取出数(匹配多位数)
  81.             if (item.matches("\\d+")) { 
  82.                 // 入栈
  83.                 stack.push(item);
  84.             } else { 
  85.                 // pop 出两个数，并运算，再入栈
  86.                 int num2 = Integer.parseInt(stack.pop());
  87.                 int num1 = Integer.parseInt(stack.pop());
  88.                 int res = 0;
  89.                 switch (item) { 
  90.                     case Constants.ADD_SYMBOL:
  91.                         res = num1 + num2;
  92.                         break;
  93.                     case Constants.SUB_SYMBOL:
  94.                         res = num1 - num2;
  95.                         break;
  96.                     case Constants.MUL_SYMBOL:
  97.                         res = num1 * num2;
  98.                         break;
  99.                     case Constants.DIV_SYMBOL:
  100.                         res = num1 / num2;
  101.                         break;
  102.                     default:
  103.                         throw new RuntimeException("运算符有误");
  104.                 }
  106.                 // 把 res 入栈
  107.                 stack.push("" + res);
  108.             }
  109.         }
  110.         // 最后留在 stack 中的数据是运算结果
  111.         return Integer.parseInt(stack.pop());
  112.     }
  113. }

编写测试方法。

  1. public class Test { 
  3.     public static void main(String[] args) { 
  4.         String expression = "1+((2+3)*4)-5";
  5.         List<String> infixExpressionToList = ReversePolandCalculator.infixExpressionToList(expression);
  6.         System.out.println("中缀表达式对应的 List=" + infixExpressionToList);
  8.         List<String> suffixExpressionList = ReversePolandCalculator.infixToSuffixExpressionList(infixExpressionToList);
  9.         System.out.println("后缀表达式对应的 List=" + suffixExpressionList);
  11.         // 计算表达式的值
  12.         System.out.printf("expression=%d", ReversePolandCalculator.calculate(suffixExpressionList));
  13.     }
  15. }

输出结果：

  1. 中缀表达式对应的 List=[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
  2. 不存在该运算符
  3. 不存在该运算符
  4. 后缀表达式对应的 List=[1, 2, 3, +, 4, *, +, 5, -]
  5. expression=16

基本上一个基于栈的逆波兰计算器就实现了。下面给出完整的逆波兰计算器代码，不仅支持多位数，还支持小数。还可以处理任何空白字符串，包括空格、制表符、换页符。

逆波兰计算器完成版

创建一个常量类

  1. public class Constants { 
  3.     public static final String LEFT = "(";
  5.     public static final String RIGHT = ")";
  7.     public static final String ADD = "+";
  9.     public static final String MINUS = "-";
  11.     public static final String TIMES = "*";
  13.     public static final String DIVISION = "/";
  15.     /** * 运算符级别： + - */
  16.     public static final int LEVEL_1 = 1;
  18.     /** * 运算符级别：* / */
  19.     public static final int LEVEL_2 = 2;
  21.     /** * int 的 最大值(代表括号的等级) */
  22.     public static final int LEVEL_HIGH = Integer.MAX_VALUE;
  24. }

提取公共方法

  1. public class CommonUtils { 
  3.     /** * TODO 匹配运算符 */
  4.     public static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";
  5.     private static final Pattern PATTERN = Pattern.compile("^[-\\+]?[.\\d]*$");
  7.     /** * TODO 去除所有 空白字符 * * @param str * @return java.lang.String */
  8.     public static String replaceAllBlank(String str) { 
  9.         // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
  10.         return str.replaceAll("\\s+", "");
  11.     }
  13.     /** * TODO 判断是不是数字 * * @param str * @return boolean */
  14.     public static boolean isNumber(String str) { 
  15.         return PATTERN.matcher(str).matches();
  16.     }
  18.     /** * TODO 判断 是不是 运算符 * * @param str * @return boolean */
  19.     public static boolean isSymbol(String str) { 
  20.         return str.matches(SYMBOL);
  21.     }
  23.     /** * TODO 获取运算等级 * * @param str * @return int */
  24.     public static int getLevel(String str) { 
  25.         if (Constants.ADD.equals(str) || Constants.MINUS.equals(str)) { 
  26.             return Constants.LEVEL_1;
  27.         } else if (Constants.TIMES.equals(str) || Constants.DIVISION.equals(str)) { 
  28.             return Constants.LEVEL_2;
  29.         }
  30.         return Constants.LEVEL_HIGH;
  31.     }
  32. }

编写核心的计算方法。

  1. public class Calculator { 
  3.     /** * 初始化栈 */
  4.     public static Stack<String> stack = new Stack<>();
  5.     /** * Collections.synchronizedList:集合的线程安全包装方法 */
  6.     public static List<String> data = Collections.synchronizedList(new ArrayList<>());
  8.     /** * TODO 匹配 * * @param str * @return java.util.List<java.lang.String> */
  9.     public static List<String> doMatch(String str) { 
  10.         if (str == null || "".equals(str.trim())) { 
  11.             throw new RuntimeException("data is empty");
  12.         }
  13.         if (!CommonUtils.isNumber(str.charAt(0) + "")) { 
  14.             throw new RuntimeException("data illegal,start not with a number");
  15.         }
  16.         str = CommonUtils.replaceAllBlank(str);
  18.         String each;
  19.         int start = 0;
  20.         for (int i = 0; i < str.length(); i++) { 
  21.             if (CommonUtils.isSymbol(str.charAt(i) + "")) { 
  22.                 each = str.charAt(i) + "";
  23.                 //栈为空，( 操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及 是 ) 不能直接入栈
  24.                 boolean flag = stack.isEmpty() || Constants.LEFT.equals(each) || ((CommonUtils.getLevel(each) > CommonUtils.getLevel(stack.peek())) && CommonUtils.getLevel(each) < Constants.LEVEL_HIGH);
  25.                 if (flag) { 
  26.                     stack.push(each);
  27.                 } else if (!stack.isEmpty() && CommonUtils.getLevel(each) <= CommonUtils.getLevel(stack.peek())) { 
  28.                     //栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
  29.                     while (!stack.isEmpty() && CommonUtils.getLevel(each) <= CommonUtils.getLevel(stack.peek())) { 
  30.                         if (CommonUtils.getLevel(stack.peek()) == Constants.LEVEL_HIGH) { 
  31.                             break;
  32.                         }
  33.                         data.add(stack.pop());
  34.                     }
  35.                     stack.push(each);
  36.                 } else if (Constants.RIGHT.equals(each)) { 
  37.                     // ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
  38.                     while (!stack.isEmpty() && Constants.LEVEL_HIGH >= CommonUtils.getLevel(stack.peek())) { 
  39.                         if (Constants.LEVEL_HIGH == CommonUtils.getLevel(stack.peek())) { 
  40.                             stack.pop();
  41.                             break;
  42.                         }
  43.                         data.add(stack.pop());
  44.                     }
  45.                 }
  46.                 // 前一个运算符的位置
  47.                 start = i;
  49.             } else if (i == str.length() - 1 || CommonUtils.isSymbol(str.charAt(i + 1) + "")) { 
  50.                 each = start == 0 ? str.substring(start, i + 1) : str.substring(start + 1, i + 1);
  51.                 if (CommonUtils.isNumber(each)) { 
  52.                     data.add(each);
  53.                     continue;
  54.                 }
  55.                 throw new RuntimeException("data not match number");
  56.             }
  57.         }
  58.         //如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个 stack 添加到队列
  59.         Collections.reverse(stack);
  60.         data.addAll(new ArrayList<>(stack));
  62.         System.out.println(data);
  63.         return data;
  64.     }
  66.     /** * TODO 算出结果 * * @param list * @return java.lang.Double */
  67.     public static Double calculateResult(List<String> list) { 
  68.         double res = 0D;
  69.         if (list == null || list.isEmpty()) { 
  70.             return null;
  71.         }
  72.         if (list.size() == 1) { 
  73.             System.out.println(list);
  74.             res = Double.parseDouble(list.get(0));
  75.             return res;
  76.         }
  77.         ArrayList<String> list1 = new ArrayList<>();
  78.         for (int i = 0; i < list.size(); i++) { 
  79.             list1.add(list.get(i));
  80.             if (CommonUtils.isSymbol(list.get(i))) { 
  81.                 Double d = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
  82.                 list1.remove(i);
  83.                 list1.remove(i - 1);
  84.                 list1.set(i - 2, d + "");
  85.                 list1.addAll(list.subList(i + 1, list.size()));
  86.                 break;
  87.             }
  88.         }
  89.         calculateResult(list1);
  90.         return res;
  91.     }
  93.     /** * TODO 运算 * * @param str1 * @param str2 * @param symbol * @return java.lang.Double */
  94.     public static Double doTheMath(String str1, String str2, String symbol) { 
  95.         Double result;
  96.         switch (symbol) { 
  97.             case Constants.ADD:
  98.                 result = new BigDecimal(str1).add(new BigDecimal(str2)).setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
  99.                 break;
  100.             case Constants.MINUS:
  101.                 result = new BigDecimal(str1).subtract(new BigDecimal(str2)).setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
  102.                 break;
  103.             case Constants.TIMES:
  104.                 result = new BigDecimal(str1).multiply(new BigDecimal(str2)).setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
  105.                 break;
  106.             case Constants.DIVISION:
  107.                 result = new BigDecimal(str1).divide(new BigDecimal(str2)).setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
  108.                 break;
  109.             default:
  110.                 result = null;
  111.         }
  112.         return result;
  113.     }
  114. }

编写测试类。

  1. public static void main(String[] args) { 
  2.         String math = "9+(3-1)*3+10/2";
  3.         try { 
  4.             calculateResult(doMatch(math));
  5.         } catch (Exception e) { 
  6.             e.printStackTrace();
  7.         }
  8.     }

输出结果：

  1. [9, 3, 1, -, 3, *, +, 10, 2, /, +]
  2. [20.0]

逆波兰计算器的实现就到这里结束了，其中存在很多问题。如果想实现一个完整的计算器，还有很多细节需要考虑进去。数据结构也是一步一步学习的。慢慢理解才能变的透彻。

参考资料：
作者：韩顺平
课程：《Java数据结构与算法》

发表评论

表情：
评论列表 （有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Java代码实现逆波兰计算器

    关于逆波兰计算器，需求如下 输入一个逆波兰表达式（后缀表达式），使用栈（Stack），计算其结果，只支持对整数的计算即可。 思路分析 后缀表达式又称逆波兰表达式，与

    小咪咪小咪咪/ 0 赞/ 80 阅读

    相关 逆波兰计算器

    该版本只支持整数类型数进行计算 本文主要是对逆波兰计算器的原理介绍和代码实现，所以对前缀、中缀、后缀表达式不做过多的赘述，下面先简单介绍一下后缀表达式 后缀表达式又称逆波兰

    深藏阁楼爱情的钟深藏阁楼爱情的钟/ 0 赞/ 206 阅读

    相关 逆波兰计算器

    > 逆波兰表达式又叫做后缀表达式，逆波兰表达式把运算量写在前面,把运算符写在后面。 我们平时书写的表达式都是中缀表达式，这个表达式更加方便我们进行计算。但是相对于计算机而言，

    短命女短命女/ 0 赞/ 186 阅读

    相关 逆波兰计算器

    一 整体算法 1 输入一个中缀表达式。 2 将中缀表达式转换为后缀表达式（逆波兰表达式）。 3 根据逆波兰表达式求算最后的结果。 二 将中缀表达式转换为后缀表达式

    川长思鸟来川长思鸟来/ 0 赞/ 402 阅读

    相关 逆波兰计算器完整版

    一 需求 完整版的逆波兰计算器，功能包括如下： 1 支持 + - \ / ( ) 2 多位数，支持小数 3 兼容处理, 过滤任何空白字符，包括空格、制表符、换页符

    r囧r小猫r囧r小猫/ 0 赞/ 438 阅读