1. 全栈程序员必看首页

计算中缀表达式

全栈程序员-站长 • • 未分类 • 阅读 2

计算中缀表达式转载自 https blog csdn net article details 计算中缀表达式 可以称得上是一个特别经典的关于栈的算法题 几乎在所有数据结构教材中都会涉及 而且很多公司面试或者笔试的时候都会把这道题作为一个考察点 可以说 这是一道必须要掌握的算法题 中缀表达式 后缀表达式等概念在这里就不赘述了 让我们直奔主题 题目 输入一个中缀表达式 计

转载自https://blog.csdn.net/_/article/details/

“计算中缀表达式”可以称得上是一个特别经典的关于栈的算法题，几乎在所有数据结构教材中都会涉及，而且很多公司面试或者笔试的时候都会把这道题作为一个考察点。可以说，这是一道必须要掌握的算法题。中缀表达式、后缀表达式等概念在这里就不赘述了，让我们直奔主题。

题目：输入一个中缀表达式，计算其结果。

输入的前提假设：

（1）只考虑+、-、*、/这四种运算符，中缀表达式中只有一种括号：（）；

（2）输入的中缀表达式中只有整数，没有小数；

（3）假定输入是合法的。

很多文章或课本喜欢一步到位，直接讨论如何从中缀表达式计算结果。但对于初学者来说，跨度未免大了点。这里循序渐进，从易到难，先讨论如何将中缀表达式转化为后缀表达式，再讨论如何计算后缀表达式。最后在前面两步的基础上，讨论如何一步到位，直接计算中缀表达式的结果：

一、如何将中缀表达式转化为后缀表达式

在日常应用中，算术表达式中运算符总是出现在两个操作数之间，例如5*（7-2*3）+8/2，这种形式称为中缀表达式。计算一个中缀表达式需要知道运算符的优先级和结合性。乘除是高优先级，加减是低优先级，优先级相同时他们都是左结合的，也就是从左计算到右。有括号就要计算括号内的表达式。

中缀表达式利于人的理解，但不便于计算机的处理。因此需要将中缀表达式转换成后缀表达式，以方便计算机处理。所谓后缀表达式就是将运算符放在运算数之后。后缀表达式也称为逆波兰表达式。

比如：

中缀表达式为：1+(2-3)*4+4/2

对应后缀表达式为：1 2 3 – 4* + 4 2 / +

如何将一个中缀表达式转化为后缀表达式？我们需要借助栈的力量，用它来存放运算符。算法流程如下：

首先将各种运算符（包括括号）的优先级排列如下（数字越大，优先级越高）：

1：（

2：+ –

3：* /

4：）

对输入的中缀表达式从左到右遍历：

1）如果遇到数字，直接添加到后缀表达式末尾；

2）如果遇到运算符+、-、*、/：

先判断栈是否为空。若是，则直接将此运算符压入栈。若不是，则查看当前栈顶元素。若栈顶元素优先级大于或等于此操作符级别，则弹出栈顶元素，将栈顶元素添加到后缀表达式中，并继续进行上述判断。如果不满足上述判断或者栈为空，将这个运算符入栈。要注意的是，经过上述步骤，这个运算符最终一定会入栈。

3）如果遇到括号：

如果是左括号，直接入栈。如果是右括号，弹出栈中第一个左括号前所有的操作符，并将左括号弹出。（右括号别入栈）。

4）字符串遍历结束后，如果栈不为空，则弹出栈中所有元素，将它们添加到后缀表达式的末尾，直到栈为空。

二、计算后缀表达式

后缀表达式的计算就相当简单了。准备一个数字栈。从左到右扫描后缀表达式，如果是数字，放入数字栈。如果是符号，从数字栈中弹出两个数字，第一个取出的数字为右运算数，第二个为左运算数，进行运算。然后将结果放进数字栈中。如此反复，直到读完整个表达式后，留在数字栈中的那个数字就是最终结果。

C++代码如下，要注意，下面的代码默认中缀表达式中所有数字都是整数，并且都在0到9之间。而且计算结果都是整数（比如5/2=2）。

[cpp] 
view plain  
copy

  1. #include
      
  2. #include
      
  3. #include
      
  4.   
  5. using namespace std;  
  6.   
  7. int getPriority(char ch)  
  8. {  
  9.     //获取优先级  
  10.     if (ch == ‘(‘) return 1;  
  11.     else if (ch == ‘+’ || ch == ‘-‘) return 2;  
  12.     else if (ch == ‘*’ || ch == ‘/’) return 3;  
  13.     else return 4;  
  14. }  
  15.   
  16. string getPostfixExpression(string str)  
  17. {  
  18.     //将中缀表达式转化为后缀表达式  
  19.     //默认输入是合法的  
  20.     stack<char> mystack;  
  21.     int size = str.size();  
  22.     int i = 0;  
  23.     char tmp;  
  24.     string res = “”;  
  25.     while (i < size) {  
  26.         if (str[i] >= ‘0’ && str[i] <= ‘9’){  
  27.             res.push_back(str[i]);  
  28.         }  
  29.         elseif (str[i] == ‘+’ || str[i] == ‘-‘ || str[i] == ‘*’ || str[i] == ‘/’) {  
  30.             if (mystack.empty()) {  
  31.                 mystack.push(str[i]);  
  32.             }  
  33.             else {  
  34.                 while (!mystack.empty()) {  
  35.                     tmp = mystack.top();  
  36.                     if (getPriority(tmp) >= getPriority(str[i])) {  
  37.                         //弹出栈顶元素  
  38.                         res.push_back(tmp);  
  39.                         mystack.pop();  
  40.                     }  
  41.                     else break;  
  42.                 }  
  43.                 mystack.push(str[i]);  
  44.             }  
  45.         }  
  46.         else {  
  47.             if(str[i]==‘(‘) mystack.push(str[i]);  
  48.             else {  
  49.                 while (mystack.top() != ‘(‘) {  
  50.                     tmp = mystack.top();  
  51.                     res.push_back(tmp);  
  52.                     mystack.pop();  
  53.                 }  
  54.                 mystack.pop();  
  55.             }  
  56.         }  
  57.         i++;  
  58.     }  
  59.   
  60.     //遍历完后，若栈非空，弹出所有元素  
  61.     while (!mystack.empty()) {  
  62.         tmp = mystack.top();  
  63.         res.push_back(tmp);  
  64.         mystack.pop();  
  65.     }  
  66.     return res;  
  67. }  
  68.   
  69.    
  70.   
  71. int calculator(string str)  
  72. {  
  73.     //计算后缀表达式的值，默认中缀表达式所有数字都是一位的，在0-9之间  
  74.     stack<int> mystack;  
  75.     int size = str.size();  
  76.     int num1, num2, num3;  
  77.     for (int i = 0; i < size; i++) {  
  78.         if (str[i] >= ‘0’ && str[i] <= ‘9’) {  
  79.             mystack.push(str[i] – ‘0’);  
  80.         }  
  81.         else {  
  82.             num2 = mystack.top();  
  83.             mystack.pop();  
  84.             num1 = mystack.top();  
  85.             mystack.pop();  
  86.             if (str[i] == ‘+’) {  
  87.                 num3 = num1 + num2;  
  88.             }  
  89.             else if (str[i] == ‘-‘) {  
  90.                 num3 = num1 – num2;  
  91.             }  
  92.             else if (str[i] == ‘*’) {  
  93.                 num3 = num1 * num2;  
  94.             }  
  95.             else if (str[i] == ‘/’) {  
  96.                 num3 = num1 / num2;  
  97.             }  
  98.             mystack.push(num3);  
  99.         }  
  100.     }  
  101.     return mystack.top();  
  102. }  
  103.   
  104.    
  105. int main()  
  106. {  
  107.     string str=“1+(2-3)*4+4/2”;  
  108.     cout <<“中缀表达式为:”<< endl << str << endl;  
  109.     string res = getPostfixExpression(str);  
  110.     cout <<“后缀表达式为:”<< endl << res << endl;  
  111.     int num_res = calculator(res);  
  112.     cout <<“计算结果:”<< endl << num_res << endl;  
  113.     system(“pause”);  
  114.     return 0;  
  115. }  

三、直接计算中缀表达式

其实将前面的两步结合起来，就可以得到直接计算的方法。准备一个数字栈和一个符号栈。

从左到右遍历中缀表达式。如果遇到数字，入数字栈。

如果遇到符号（四个运算符以及括号），跟前面的“中缀表达式转后缀表达式”过程一样，对符号栈进行处理。处理过程中，对每一个出栈的运算符：+ – * /，根据“计算后缀表达式”的方法，计算结果（跟数字栈配合）。

如果遍历完中缀表达式后符号栈还非空，就继续出符号栈的运算符，计算，直到符号栈为空。最后数字栈剩下的数字就是结果。

下面给出用C++实现“计算中缀表达式”的代码，里面考虑了“数字不止1位”，并且用浮点型来表示最终运算结果。要求中缀表达式中只能包含整数和运算符（不能包含小数），并且是合法的。

[cpp] 
view plain  
copy

  1. #include
      
  2. #include
      
  3. #include
      
  4.   
  5. using namespace std;  
  6.   
  7. int getPriority(char ch)  
  8. {  
  9.     //获取优先级  
  10.     if (ch == ‘(‘) return 1;  
  11.     else if (ch == ‘+’ || ch == ‘-‘) return 2;  
  12.     else if (ch == ‘*’ || ch == ‘/’) return 3;  
  13.     else return 4;  
  14. }  
  15.   
  16. void calculate(stack<double> &mystack, char operation)  
  17. {  
  18.     double num1, num2, num3;  
  19.     num2 = mystack.top();  
  20.     mystack.pop();  
  21.     num1 = mystack.top();  
  22.     mystack.pop();  
  23.     if (operation == ‘+’) {  
  24.         num3 = num1 + num2;  
  25.     }  
  26.     else if (operation == ‘-‘) {  
  27.         num3 = num1 – num2;  
  28.     }  
  29.     else if (operation == ‘*’) {  
  30.         num3 = num1 * num2;  
  31.     }  
  32.     else if (operation == ‘/’) {  
  33.         num3 = num1 / num2;  
  34.     }  
  35.   
  36.     mystack.push(num3);  
  37. }  
  38.   
  39. double calculator(string str)  
  40. {  
  41.     //计算中缀表达式,默认输入是合法的  
  42.     stack<double> mystack_number;  
  43.     stack<char> mystack_operation;  
  44.     int i = 0, j;  
  45.     int size = str.size();  
  46.     char tmp_operation;  
  47.     string tmp_num;  
  48.     while (i < size) {  
  49.         if (str[i] >= ‘0’ && str[i] <= ‘9’) {  
  50.             j = i;  
  51.             while (j < size && str[j] >= ‘0’ && str[j] <= ‘9’) { j++; }  
  52.             tmp_num = str.substr(i, j – i);  
  53.             mystack_number.push(atoi(tmp_num.c_str()));  
  54.             i = j;  
  55.         }  
  56.         else if (str[i] == ‘+’ || str[i] == ‘-‘ || str[i] == ‘*’ || str[i] == ‘/’) {  
  57.             if (mystack_operation.empty()) {  
  58.                 mystack_operation.push(str[i]);  
  59.             }  
  60.             else {  
  61.                 while (!mystack_operation.empty()) {  
  62.                     tmp_operation = mystack_operation.top();  
  63.                     if (getPriority(tmp_operation) >= getPriority(str[i])) {  
  64.                         //计算  
  65.                         calculate(mystack_number, tmp_operation);  
  66.                         mystack_operation.pop();  
  67.                     }  
  68.                     else break;  
  69.                 }  
  70.                 mystack_operation.push(str[i]);  
  71.             }  
  72.             i++;  
  73.         }  
  74.         else {  
  75.             if (str[i] == ‘(‘) mystack_operation.push(str[i]);  
  76.             else {  
  77.                 while (mystack_operation.top() != ‘(‘) {  
  78.                     tmp_operation = mystack_operation.top();  
  79.                     //计算  
  80.                     calculate(mystack_number, tmp_operation);  
  81.                     mystack_operation.pop();  
  82.                 }  
  83.                 mystack_operation.pop();  
  84.             }  
  85.             i++;  
  86.         }  
  87.   
  88.     }  
  89.     //遍历完后，若栈非空，弹出所有元素  
  90.     while (!mystack_operation.empty()) {  
  91.         tmp_operation = mystack_operation.top();  
  92.         //计算  
  93.         calculate(mystack_number, tmp_operation);  
  94.         mystack_operation.pop();  
  95.     }  
  96.     return mystack_number.top();  
  97. }  
  98.   
  99. int main()  
  100. {  
  101.     string str = “1+(2-3)*4+10/2+2*2+2+2/5”;  
  102.     cout << “中缀表达式为:” << endl << str << endl;  
  103.     double num_res = calculator(str);  
  104.     cout << “计算结果:” << endl << num_res << endl;  
  105.     system(“pause”);  
  106.     return 0;  
  107. }  


计算中缀表达式

相信通过这篇文章，大家对这个问题会有所了解。

给出一道思考题：如果加入乘方’^’，应该如何处理？要注意，乘方运算是右结合的。

其实很简单。只有两处修改：

1）将乘方添加到优先级中：

1：（

2：+ –

3：* /

4：^

5：）

2）在读中缀表达式的时候，如果读到乘方^，就将它放进符号栈中。因为乘方的优先级是最高的，而且是右结合的，所以无论它前面出现的是什么运算，这些运算都不能执行。而且它本身能否执行也是不知道的，因此只能进栈。

大家自己试试吧~要记住，学习编程，动手去写代码永远是第一位的。

【参考资料】

[2]翁惠玉, 俞勇. 数据结构:思想与实现[M]. 高等教育出版社, 2009.


版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/222283.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月17日 下午4:08
下一篇 2026年3月17日 下午4:09


相关推荐

  • java测试面试问题_struts2面试题

    java测试面试问题_struts2面试题

    java测试面试问题_struts2面试题Javashiro面试题1、简单介绍一下Shiro框架？ApacheShiro是Java的一个安全框架。使用Shiro可以非常容易的开发出足够好的应用。其不仅可以用在JavaSE环境，也可以用在JavaEE环境。Shiro可以帮助我们完成功能：认证、授权、加密、会话管理、与Web集成、缓存等。三个核心组件：Subject，SecurityManager和Realms。●Subject：即“当…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年10月14日
    4
  • 【NOIP2011提高组】选择客栈

    【NOIP2011提高组】选择客栈

    【NOIP2011提高组】选择客栈题目背景NOIP2011提高组 DAY1 试题。题目描述丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ～ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们…

    全栈程序员-站长的头像 全栈程序员-站长
    2025年12月7日
    9
  • pfx 证书导出公钥和私钥「建议收藏」

    pfx 证书导出公钥和私钥「建议收藏」

    pfx 证书导出公钥和私钥「建议收藏」pfx证书导出公钥和私钥在做银联支付的时候，因为是多商户的，所以采用单独的私钥加密，需要提取pfx中的私钥准备准备pfx格式的证书[root@blueacp_crt]#tree.├──acp_test_sign.pfx提取密钥对格式:opensslpkcs12-inacp_test_sign.pfx-nocerts-nodes-outacp_test_sign.key[root@blueacp_crt]#opensslpkcs12-inacp_t

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月10日
    48
  • 图集谷-写真集-爬虫-2.1「建议收藏」

    图集谷-写真集-爬虫-2.1「建议收藏」

    图集谷-写真集-爬虫-2.1「建议收藏」图集谷爬虫2.0版本的修改版本

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月27日
    104
  • spring任务调度scheduled_golang 任务调度

    spring任务调度scheduled_golang 任务调度

    spring任务调度scheduled_golang 任务调度1、任务调度接口TaskScheduler提供了多种方法来调度将来某个时间点要运行的任务。2、触发器Trigger实现PeriodicTrigger和CronTrigger。3、@Scheduled注解创建定时任务4、@Async注解异步方法执行，value属性指定任务执行器。5、task:scheduler、task:executor创建调度器和执行器…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年10月11日
    5
  • java简单加密解密_md5加密解密代码

    java简单加密解密_md5加密解密代码

    java简单加密解密_md5加密解密代码using System;using System.Text; namespace Common{/// <summary>///&#16

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月5日
    7

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号