经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 其他 » 计算机原理 » 查看文章
计算器思想-中缀表达式转化为后缀表达式
来源：cnblogs　　作者：pretty_spider　　时间：2023/9/15 13:31:21　　对本文有异议

计算机思维和人的思维的不同

对于一个算式3+2*（4-3)/5
人的思维是根据括号和符号优先级，优先计算括号中的数据，在进行乘法和除法，在处理加法运算
但是计算机的思维是线性的，计算机会按照算式的前后顺序，从前往后进行运算，这样会导致运算结果错误

计算机如何套用人的运算思维

想要让计算机具有人的”思维“，就需要使用栈，将数据和运算符号之间的顺序按照计算机可以理解的方式排列
想要改变规则，就需要将人理解的中缀表达式转换为后缀表达式
转化的规则是：

  • 中缀表达式转化成后缀表达式
    1.遇到操作数直接放入到集合中
    2.遇到操作符
    2.1当栈为空，或栈顶元素为（，直接放入到栈中
    2.2当优先级比栈顶元素高时，直接进栈
    2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
    3.遇到左右括号
    3.1如果为左括号，直接加入栈
    3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
    4.最后将栈顶元素依次弹出

中缀表达式转换为后缀表达式的过程

以运算算式 3-（4-3）/5*10
以中缀表达式表示为 3 - 4 - 3 / 5 * 10
后缀表达式表示为 3 4 3 - 5 / 10 * -
其中涉及到了栈的入栈和出栈，

转化过程：
1.先创建一个集合，用于记录后缀表达式，创建一个栈，用于记录运算符
2.3进入集合，-进入栈 集合 3 栈 -
3.左括号进栈 集合3 栈- （
4.4进入集合，-进入栈，与此时的栈顶元素比较，此时栈顶元素是左括号，-直接放入栈中 集合3 4 栈 - （ -
5.3进入集合，-和栈顶元素比较，优先级相等或者小于，将栈顶元素-弹出 集合中为 3 4 3 - 栈-（
6.右括号进栈 将栈顶元素弹出，直到左括号并弹出左括号 集合3 4 3 - 栈-
7./进栈，优先级大于-，直接进栈，5 进入集合 集合3 4 3 - 5 栈- /
8.*进栈，优先等于栈顶元素，弹出栈顶元素，10进入集合 集合 3 4 3 - 5 / 10 栈 - *
9.算式获取完成，将栈中元素全部弹出 集合 3 4 3 - 5 / 10 * -

实现

整数算式运算

  1. package com.prettyspider.calculate;
  3. import java.util.*;
  6. /**
  7.  * @author prettyspider
  8.  * @ClassName CalcInt
  9.  * @description: 传入整数运算字符串，计算其数值
  10.  * @date 2023/9/11 6:21
  11.  * @Version V1.0
  12.  */
  14. public class CalcInt {
  15.     /**
  16.      * 中缀表达式转化成后缀表达式
  17.      * <p>
  18.      * 1.遇到操作数直接放入到集合中
  19.      * 2.遇到操作符
  20.      * 2.1当栈为空，或栈顶元素为（，直接放入到栈中
  21.      * 2.2当优先级比栈顶元素高时，直接进栈
  22.      * 2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
  23.      * 3.遇到左右括号
  24.      * 3.1如果为左括号，直接加入栈
  25.      * 3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
  26.      * 4.最后将栈顶元素依次弹出
  27.      */
  28.     public static void main(String[] args) {
  29.         // 要传入的运算字符串
  30.         String s = "10+2*(3-4)+20*(3*4+3)/3+20";
  31.         // 中缀表达式转化成后缀表达式
  32.         List<String> list = inToPastExpression(s);
  33.         // 计算
  34.         int number = calc(list);
  35.         System.out.println("计算的数值为"+number);
  36.     }
  39.     /**
  40.      * 计算后缀表达式
  41.      * @param list 后缀表达式集合
  42.      * @return 传入的整数运算字符串的计算数值
  43.      */
  44.     private static int calc(List<String> list) {
  45.         // 创建栈，用于记录数据
  46.         Stack<String> stack = new Stack<>();
  47.         for (String s : list) {
  48.             // 1.放入 当是数值时，直接放入栈中
  49.             if (s.matches("\\d+")) {
  50.                 stack.push(s);
  51.             } else {
  52.                 // 2.去除 当是运算符时，再栈中取出两个数，进行运算，并将运算之后的结果放入到栈中
  53.                 int num1, num2;
  54.                 switch (s) {
  55.                     case "+":
  56.                         num1 = Integer.parseInt(stack.pop());
  57.                         num2 = Integer.parseInt(stack.pop());
  58.                         stack.push(String.valueOf(num2 + num1));
  59.                         break;
  60.                     case "-":
  61.                         num1 = Integer.parseInt(stack.pop());
  62.                         num2 = Integer.parseInt(stack.pop());
  63.                         stack.push(String.valueOf(num2 - num1));
  64.                         break;
  65.                     case "*":
  66.                         num1 = Integer.parseInt(stack.pop());
  67.                         num2 = Integer.parseInt(stack.pop());
  68.                         stack.push(String.valueOf(num2 * num1));
  69.                         break;
  70.                     case "/":
  71.                         num1 = Integer.parseInt(stack.pop());
  72.                         num2 = Integer.parseInt(stack.pop());
  73.                         stack.push(String.valueOf(num2 / num1));
  74.                         break;
  75.                 }
  76.             }
  77.         }
  78.         return Integer.parseInt(stack.pop());
  79.     }
  82.     /**
  83.      * 将传入的字符串进行切分，存放到集合中
  84.      * @param str 传入的算数字符串
  85.      * @return 后缀表达式集合
  86.      */
  87.     private static List<String> inToPastExpression(String str) {
  88.         // 创建集合和栈
  89.         List<String> list = new ArrayList<>();
  90.         Stack<String> stack = new Stack<>();
  91.         // 切分数据
  92.         ArrayList<String> arr = cutString(str);
  93.         for (int i = 0; i < arr.size(); i++) {
  94.             //       * 1.遇到操作数直接放入到集合中
  95.             String value = arr.get(i);
  96.             if (value.matches("\\d+")) {
  97.                 list.add(value);
  98.             }
  99.             //      * 3.遇到左右括号
  100.             //      *      3.1如果为左括号，直接加入群
  101.             else if ("(".equals(value)) {
  102.                 stack.push(value);
  103.             }
  104.             //      *      3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
  105.             else if (")".equals(value)) {
  106.                 while (!"(".equals(stack.peek())) {
  107.                     list.add(stack.pop());
  108.                 }
  109.                 stack.pop();
  110.             }
  111.             //      * 2.遇到操作符
  112.             else {
  113.                 //      *      2.1当栈为空，或栈顶元素为（，直接放入到栈中
  114.                 //      *      2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
  115.                 while (stack.size() != 0 && !judgeOperator(value, stack.peek())) {
  116.                     list.add(stack.pop());
  117.                 }
  118.                 //      *      2.2当优先级比栈顶元素高时，直接进栈
  119.                 stack.push(value);
  120.             }
  121.         }
  122.         //      * 4.最后将栈顶元素依次弹出
  123.         while (!stack.empty()) {
  124.             list.add(stack.pop());
  125.         }
  126.         System.out.println(list);
  127.         return list;
  128.     }
  130.     /**
  131.      * 将运算字符切分切分成集合
  132.      * @param str 待切分字符串
  133.      * @return ArrayList<String> 被切分之后的字符串集合
  134.      */
  135.     private static ArrayList<String> cutString(String str) {
  136.         String[] arr = new String[str.length()-1];
  137.         // 为字符串数组赋初值
  138.         for (int i = 0; i < arr.length; i++) {
  139.             arr[i] = "";
  140.         }
  141.         int index = 0;
  142.         arr[index] = String.valueOf(str.charAt(0));
  143.         for (int i = 1; i < str.length(); i++) {
  144.             // 1.是数值放入
  145.             if (Character.isDigit(str.charAt(i))) {
  146.                 // 1.1并看其起一个数据是不是也数值，是数值，将其前一个数据*10+本身
  147.                 if (arr[index].matches("\\d+")) {
  148.                     arr[index] = String.valueOf(Integer.parseInt(arr[index]) * 10 + Integer.parseInt(String.valueOf(str.charAt(i))));
  149.                 } else {
  150.                     arr[++index] = String.valueOf(str.charAt(i));
  151.                 }
  152.             } else {
  153.                 // 2.不是数值，直接加入到集合中
  154.                 arr[++index] = String.valueOf(str.charAt(i));
  155.             }
  156.         }
  157.         // 去除null
  158.         ArrayList<String> list = removeNull(arr);
  159.         return list;
  161.     }
  163.     /**
  164.      * 将字符串数组中为空的元素去除
  165.      * @param arr 字符串数组
  166.      * @return 去除控制的字符串集合
  167.      */
  168.     private static ArrayList<String> removeNull(String[] arr) {
  169.         ArrayList<String> list = new ArrayList<>();
  170.         for (String s : arr) {
  171.             if (!"".equals(s)) {
  172.                 list.add(s);
  173.             }
  174.         }
  175.         return list;
  176.     }
  178.     /**
  179.      * 比较新旧操作符的权重，判断是存放还是取出
  180.      * @param s1 新的操作符
  181.      * @param s2 旧的操作符
  182.      * @return 新旧操作符的权重比较
  183.      */
  184.     private static boolean judgeOperator(String s1, String s2) {
  185.         int num1 = 0, num2 = 0;
  186.         switch (s1) {
  187.             case "+":
  188.             case "-":
  189.                 num1 = 1;
  190.                 break;
  191.             case "*":
  192.             case "/":
  193.                 num1 = 2;
  194.                 break;
  195.         }
  196.         switch (s2) {
  197.             case "+":
  198.             case "-":
  199.                 num2 = 1;
  200.                 break;
  201.             case "*":
  202.             case "/":
  203.                 num2 = 2;
  204.                 break;
  205.         }
  206.         // 判断新旧操作符的优先级
  207.         if (num1 > num2) {
  208.             return true;
  209.         }
  210.         return false;
  211.     }
  212. }

小数算式运算

小数运算要考虑小数点，相对于整数要比较的复杂
在获取娴熟时，需要对小数点的位置进行判断，对小数点右边的数据进行处理

  1. package com.prettyspider.calculate;
  3. import java.util.*;
  6. /**
  7.  * @author prettyspider
  8.  * @ClassName CalcInt
  9.  * @description: 传入整数运算字符串，计算其数值
  10.  * @date 2023/9/11 6:21
  11.  * @Version V1.0
  12.  */
  14. public class CalcDouble {
  15.     /**
  16.      * 中缀表达式转化成后缀表达式
  17.      * <p>
  18.      * 1.遇到操作数直接放入到集合中
  19.      * 2.遇到操作符
  20.      * 2.1当栈为空，或栈顶元素为（，直接放入到栈中
  21.      * 2.2当优先级比栈顶元素高时，直接进栈
  22.      * 2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
  23.      * 3.遇到左右括号
  24.      * 3.1如果为左括号，直接加入栈
  25.      * 3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
  26.      * 4.最后将栈顶元素依次弹出
  27.      */
  28.     public static void main(String[] args) {
  29.         // 要传入的运算字符串
  30.         String s = "10.32*3.23+2.234";
  31.         // 中缀表达式转化成后缀表达式
  32.         List<String> list = inToPastExpression(s);
  33.         // 计算
  34.         double number = calc(list);
  35.         System.out.println("计算的数值为"+number);
  36.     }
  39.     /**
  40.      * 计算后缀表达式
  41.      * @param list 后缀表达式集合
  42.      * @return 传入的整数运算字符串的计算数值
  43.      */
  44.     private static double calc(List<String> list) {
  45.         // 创建栈，用于记录数据
  46.         Stack<String> stack = new Stack<>();
  47.         for (String s : list) {
  48.             // 1.放入 当是数值时，直接放入栈中
  49.             if (s.matches("(\\d|\\.)+")) {
  50.                 stack.push(s);
  51.             } else {
  52.                 // 2.去除 当是运算符时，再栈中取出两个数，进行运算，并将运算之后的结果放入到栈中
  53.                 double num1, num2;
  54.                 switch (s) {
  55.                     case "+":
  56.                         num1 = Double.valueOf(stack.pop());
  57.                         num2 = Double.valueOf(stack.pop());
  58.                         stack.push(String.valueOf(num2 + num1));
  59.                         break;
  60.                     case "-":
  61.                         num1 = Double.valueOf(stack.pop());
  62.                         num2 = Double.valueOf(stack.pop());
  63.                         stack.push(String.valueOf(num2 - num1));
  64.                         break;
  65.                     case "*":
  66.                         num1 = Double.valueOf(stack.pop());
  67.                         num2 = Double.valueOf(stack.pop());
  68.                         stack.push(String.valueOf(num2 * num1));
  69.                         break;
  70.                     case "/":
  71.                         num1 = Double.valueOf(stack.pop());
  72.                         num2 = Double.valueOf(stack.pop());
  73.                         stack.push(String.valueOf(num2 / num1));
  74.                         break;
  75.                 }
  76.             }
  77.         }
  78.         return Double.valueOf(stack.pop());
  79.     }
  82.     /**
  83.      * 将传入的字符串进行切分，存放到集合中
  84.      * @param str 传入的算数字符串
  85.      * @return 后缀表达式集合
  86.      */
  87.     private static List<String> inToPastExpression(String str) {
  88.         // 创建集合和栈
  89.         List<String> list = new ArrayList<>();
  90.         Stack<String> stack = new Stack<>();
  91.         // 切分数据
  92.         ArrayList<String> arr = cutString(str);
  93.         for (int i = 0; i < arr.size(); i++) {
  94.             //       * 1.遇到操作数直接放入到集合中
  95.             String value = arr.get(i);
  96.             if (value.matches("(\\d|\\.)+")) {
  97.                 list.add(value);
  98.             }
  99.             //      * 3.遇到左右括号
  100.             //      *      3.1如果为左括号，直接加入群
  101.             else if ("(".equals(value)) {
  102.                 stack.push(value);
  103.             }
  104.             //      *      3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
  105.             else if (")".equals(value)) {
  106.                 while (!"(".equals(stack.peek())) {
  107.                     list.add(stack.pop());
  108.                 }
  109.                 stack.pop();
  110.             }
  111.             //      * 2.遇到操作符
  112.             else {
  113.                 //      *      2.1当栈为空，或栈顶元素为（，直接放入到栈中
  114.                 //      *      2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
  115.                 while (stack.size() != 0 && !judgeOperator(value, stack.peek())) {
  116.                     list.add(stack.pop());
  117.                 }
  118.                 //      *      2.2当优先级比栈顶元素高时，直接进栈
  119.                 stack.push(value);
  120.             }
  121.         }
  122.         //      * 4.最后将栈顶元素依次弹出
  123.         while (!stack.empty()) {
  124.             list.add(stack.pop());
  125.         }
  126.         return list;
  127.     }
  129.     /**
  130.      * 将运算字符切分切分成集合
  131.      * @param str 待切分字符串
  132.      * @return ArrayList<String> 被切分之后的字符串集合
  133.      */
  134.     private static ArrayList<String> cutString(String str) {
  135.         String[] arr = new String[str.length()-1];
  136.         // 为字符串数组赋初值
  137.         for (int i = 0; i < arr.length; i++) {
  138.             arr[i] = "";
  139.         }
  140.         int index = 0;
  141.         arr[index] = String.valueOf(str.charAt(0));
  142.         for (int i = 1; i < str.length(); i++) {
  143.             // 1.是数值放入
  144.             if (Character.isDigit(str.charAt(i))|| ".".equals(String.valueOf(str.charAt(i)))) {
  145.                 // 1.1并看其起一个数据是不是也数值，是数值，将其前一个数据拼接
  146.                 if (arr[index].matches("(\\d|\\.)+")) {
  147.                     arr[index] = arr[index] + str.charAt(i);
  148.                 } else {
  149.                     arr[++index] = String.valueOf(str.charAt(i));
  150.                 }
  151.             } else {
  152.                 // 2.不是数值，直接加入到集合中
  153.                 arr[++index] = String.valueOf(str.charAt(i));
  154.             }
  155.         }
  156.         // 去除null
  157.         ArrayList<String> list = removeNull(arr);
  158.         return list;
  160.     }
  162.     /**
  163.      * 将字符串数组中为空的元素去除
  164.      * @param arr 字符串数组
  165.      * @return 去除控制的字符串集合
  166.      */
  167.     private static ArrayList<String> removeNull(String[] arr) {
  168.         ArrayList<String> list = new ArrayList<>();
  169.         for (String s : arr) {
  170.             if (!"".equals(s)) {
  171.                 list.add(s);
  172.             }
  173.         }
  174.         return list;
  175.     }
  177.     /**
  178.      * 比较新旧操作符的权重，判断是存放还是取出
  179.      * @param s1 新的操作符
  180.      * @param s2 旧的操作符
  181.      * @return 新旧操作符的权重比较
  182.      */
  183.     private static boolean judgeOperator(String s1, String s2) {
  184.         int num1 = 0, num2 = 0;
  185.         switch (s1) {
  186.             case "+":
  187.             case "-":
  188.                 num1 = 1;
  189.                 break;
  190.             case "*":
  191.             case "/":
  192.                 num1 = 2;
  193.                 break;
  194.         }
  195.         switch (s2) {
  196.             case "+":
  197.             case "-":
  198.                 num2 = 1;
  199.                 break;
  200.             case "*":
  201.             case "/":
  202.                 num2 = 2;
  203.                 break;
  204.         }
  205.         // 判断新旧操作符的优先级
  206.         if (num1 > num2) {
  207.             return true;
  208.         }
  209.         return false;
  210.     }
  211. }

在获取数据时，巧妙的使用正则获取对应的数据，利于数据的处理

原文链接：https://www.cnblogs.com/prettyspider/p/17703787.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

计算机原理热门文章

  • 计算机中的存储器
  • CS144 计算机网络 Lab1：Stream Reassembler
  • 编译原理的文法和语言总结与梳理
  • 计算机程序设计并行计算概念及定义全面详解
  • 看懂了采样定理
  • 非确定的自动机NFA确定化为DFA
  • 微机原理与系统设计笔记6 | 存储器系统设计
  • 为什么寄存器比内存快？
  • 1.3：Render Pipeline and GPU Pipeline
  • CPU 和 CPU Core 有啥区别？多核 CPU？多个 CPU？

    • 计算机原理推荐文章

  • 顺序与链式二叉树的原理与实现(万字)
  • 一文全懂：独立冗余磁盘阵列（RAID）
  • 文件系统(九)：一文看懂yaffs2文件系统原理
  • 现代 CPU 技术发展
  • 从算盘到云计算：计算机发展的壮丽历程
  • 计算器思想-中缀表达式转化为后缀表达式
  • 抽象语法树AST必知必会
  • CS144 计算机网络 Lab1：Stream Reassembler
  • socket 到底是个啥
  • 2.1万字，30张图详解操作系统常见面试题（收藏版）

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号