C++ 使用栈求解中缀、后缀表达式的值 _生活百科

1. 前言表达式求值对于有知识积累的你而言，可以通过认知，按运算符的优先级进行先后运算。
但对计算机而言，表达式仅是一串普通的信息而已，需要通过编码的方式告诉计算机运算法则，这个过程中栈起到了至关重要的作用。
表达式由 2 部分组成：

操作数。
运算符。

在一个复杂的表达式中，操作数和运算符可以有多个，运算符之间存在优先级，且不同运算符所需要的操作数的数量也有差异。这时，表达式的计算过程就变得较复杂。为了简化问题，本文只限于讨论基于常量操作数和双目运算符的表达式。
在计算机中，表达式的描述可以有以下 3 种：

后缀表达式：操作数，操作数，运算符。
中缀表达式：操作数，运算符，操作数。数学上最常见的描述方式。
前缀表达式：运算符，操作数，操作数。

本文将讨论后缀表达式和中缀表达式的计算过程。
2. 中缀表达式平常所见最多的表达式是中缀表达式，如下所示：
4*6^(3+3*3-2*3)-8对中缀表达式求值时需要创建 2 个栈。

文章插图

一个用来存储运算符的栈 optStack 。
一个用来存储操作数的栈numStack 。

stack<int> numStack;stack<char> optStack;2.1 求值流程扫描整个表达式，对不同类型（操作数和运算符）的字符采用不同的处理方案。

遇到操作数时的处理方案

直接将其压入numStack中，如上述表达式中的第一个字符是 4，压入numStack栈中。

文章插图

扫描到运算符时的处理方案

如果运算符比optStack栈顶运算符的优先级高，则入栈。如果比optStack栈顶的运算符的优先级低，则弹出运算符，再从numStack栈中弹出 2 个操作数，对其进行运算，且把运算结果压入到numStack栈中。
【C++ 使用栈求解中缀、后缀表达式的值】这里就有一个问题，如何判断运算符的优先级？
基于数学常识，在常规的加减乘除四则运算表达式中：

其运算符的优先级为:() > ^ > *、/、% > +、-` 。
有括号时，先算括号内的，后算括号外的，对于多层括号，由内向外进行。
乘方连续出现时先算最右边的。

但是，这里需要知道，因为使用到了出栈、入栈操作，运算符在栈外和栈内的优先级是不一样的。
如左括号(运算符，在栈外优先级是最高的，进栈后优先级则变得最低。这个很好理解，括号的本质是界限符号（界限了一个子表达式的范围，它并不具有运算能力），为了保证左括号后面的表达式中的运算符能正常入栈，就必须降低优先级别。当左括号遇到右括号时，表示由这一对括号所标识的子表达式运算结束。