计算后缀表达式 - 算法与数据结构 - 栈的运用 -C++ 语言实现

作者：阿锋

2022 年 8 月 14 日
湖北
本文字数：2015 字
阅读完需：约 7 分钟

前言

🚀 个人主页：阿阿阿阿锋的主页_CSDN🔥 有问题欢迎指出，🔥 希望能和大家一起加油，一起进步！

🌍 另外，给大家推荐一款神器：《牛客网》🌍 无论是面试，还是刷题学习，都非常好用。而且调试在线编程题时，是可以对比测试数据对应的正确输出的。

@TOC

🍘介绍

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符是放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。如：3*(5–2)+7 对应的后缀可以表达式为：3．5．2．-*7．+@。’@’为表达式的结束符号。‘.’为操作数的结束符号。后缀表达式的一个特点就是==方便计算==。我们下面只考虑 加减乘除 四种基本运算，以及表达式中没有 负数 的情况。

🍘问题分析

那么我们如何计算一个后缀表达式呢？可以借用==栈==来实现。此外，后缀表达式也可以用一个二叉树来表示和计算，但是我们这里就不细讲啦！

思路

我们先抛开问题中一些具体的细节（如：是用‘.’作为操作数的结束符号），方便理清对于整个问题的一个思路。还是用之前那个例子：3．5．2．-*7．+@我们从后缀表达式左边开始一边读取数据一边压入栈中，当遇到了运算符时，就将栈中的操作符以及紧邻的两个操作数出栈进行相应的运算，运算结果压入栈中作为新的操作数，然后继续从表达式中读取数据。反复进行以上操作直到得到运算结果。过程如下图：

一些细节和问题

在了解了一个大概的思路之后，我们就需要考虑程序实现中的一些细节问题了。

一、数据类型处理

一个后缀表达式中有操作数这样的数字，也有运算符这样的符号，所以最终是以博主都用 char 类型进行存储的。那么我们如何从以 char 类型存储了部分表达式的栈中，将操作数和运输符分别读取出来进行运算呢？需要注意，我们在压入栈中时，是一个字符一个字符的压的，所以在栈中的多位数是倒过来的，如：123 压入栈中从栈顶开始看就是 321。下面是从栈中读取出一个操作数的代码段：

//从char型栈中读取出一个int型操作数 int get_num() {  int sum(0);  for(int i = 1; s.top() != '.'; i *= 10) {    sum += (int)(s.top() - '0') * i;    s.pop();    if(s.empty()) break;  }  return sum;}

复制代码

二、负数

虽然我们前面说了不考虑表达式中有负数的情况，但是在对表达式的计算过程中仍然可能会产生负数，不过这种情况对于博主来说稍稍好处理一点（读取表达式时，负数的负号与减法运算符相同，有歧义）。博主处理运算过程中负数的方法是，先压入一个字符 0 作为符号标记，然后将原数的相反数（就是一个非负数了）压入栈中。在出栈时如果数字串的最后一个是 0，就将数据取相反数，重新得到原来的负数。

🍘最终代码

#include<iostream>#include<stack>using namespace std;stack<char> s;int get_num();    //从栈中返回一个整型数字 int main(){  char t(0);  while(true) {    //输入     cin >> t;    if(t == '@') {      s.pop();      cout << get_num();      break;    }    s.push(t);        //见运算符    if(t == '+' || t == '-' || t == '*' || t == '/') {      //出栈运算符      s.pop();      //出栈两个数字为int型      int a(0), b(0);      s.pop();      a = get_num();//      cout << "a = " << a << endl;      s.pop();      b = get_num();//      cout << "b = " << b << endl;      //计算       int result(0);      if(t == '+') result = b + a;      else if(t == '-') result = b - a;      else if(t == '*') result = b * a;      else if(t == '/') result = b / a;//      cout << "result = " << result << endl;      if(result < 0) {        s.push('0');         result = -result;//        cout << "result = " << result << endl;      }      //结果转为char型再入栈      stack<char> c;      if(result == 0) {        s.push('0');      }      while(result != 0) {        c.push((char)(result % 10 + '0'));        result /= 10;      }      while(!c.empty()) {        s.push(c.top());        c.pop();      }      s.push('.');    }  }}//------------------------------//从char型栈中读取出一个int型操作数 int get_num() {  int sum(0);  char t(0);  for(int i = 1; s.top() != '.'; i *= 10) {    t = s.top();    sum += (int)(s.top() - '0') * i;    s.pop();    if(s.empty()) break;  }  if(t == '0') sum = -sum;  return sum;}/*测试数据3.5.2.-*7.+@10.28.30./*7.-6.+@1000.1000./5.-6.*@*/

复制代码

🍘总结

后缀表达式是一个比较经典的问题。栈的原理其实很简单，就像一个加了限制的数组，只能从同一端进出数据。但是在用栈解决一些问题时，你会发现它真的好神奇，也许这就是数据结构和算法的魅力吧！

博主水平有限，欢迎来评论区交流和指正。

你们的支持，就是博主不断创作的动力！

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/8d06d632b7ef9c1cadeeff3fd】。

阿锋

关注

还未添加个人签名 2022.08.09 加入

还未添加个人简介

发布

暂无评论

创作场景