C++ 使用栈求解中缀、后缀表达式的值

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

  • 操作数 。
  • 运算符 。
在一个复杂的表达式中,操作数和运算符可以有多个,运算符之间存在优先级,且不同运算符所需要的操作数的数量也有差异 。这时 , 表达式的计算过程就变得较复杂 。为了简化问题,本文只限于讨论基于常量操作数和双目运算符的表达式 。
在计算机中,表达式的描述可以有以下 3 种:
  • 后缀表达式:操作数,操作数 , 运算符 。
  • 中缀表达式:操作数,运算符,操作数 。数学上最常见的描述方式 。
  • 前缀表达式:运算符,操作数,操作数 。
本文将讨论后缀表达式和中缀表达式的计算过程 。
2. 中缀表达式平常所见最多的表达式是中缀表达式,如下所示:
4*6^(3+3*3-2*3)-8中缀表达式求值时需要创建 2 个栈 。
C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 一个用来存储运算符的栈 optStack
  • 一个用来存储操作数的栈numStack
stack<int> numStack;stack<char> optStack;2.1 求值流程扫描整个表达式,对不同类型(操作数和运算符)的字符采用不同的处理方案 。
  • 遇到操作数时的处理方案
直接将其压入numStack中,如上述表达式中的第一个字符是 4,压入numStack栈中 。
C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 扫描到运算符时的处理方案
如果运算符比optStack栈顶运算符的优先级高,则入栈 。如果比optStack栈顶的运算符的优先级低 , 则弹出运算符,再从numStack栈中弹出 2 个操作数,对其进行运算,且把运算结果压入到numStack栈中 。
这里就有一个问题,如何判断运算符的优先级?
基于数学常识 , 在常规的加减乘除四则运算表达式中:
  • 其运算符的优先级为:() > ^ > *、/、% > +、-` 。
  • 有括号时,先算括号内的,后算括号外的,对于多层括号,由内向外进行 。
  • 乘方连续出现时先算最右边的 。
但是,这里需要知道, 因为使用到了出栈、入栈操作 , 运算符在栈外和栈内的优先级是不一样的 。
如左括号(运算符,在栈外优先级是最高的,进栈后优先级则变得最低 。这个很好理解,括号的本质是界限符号( 界限了一个子表达式的范围,它并不具有运算能力),为了保证左括号后面的表达式中的运算符能正常入栈 , 就必须降低优先级别 。当左括号遇到右括号时,表示由这一对括号所标识的子表达式运算结束 。
Tips: 栈内、栈外优先级相同的运算符,栈内优先 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 一直反复上述过程,直到表达式扫描结束 。
2.2 演示表达式4*6^(3+3*3-2*3)-8 的求值过程
  • 当一直扫描到第一个减号(-)时,两个栈都是在进行入栈操作 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • -(减法)运算符优先级低于optStack栈顶的*运算符 。这时从optStack栈中弹出*,再从numStack中弹出33 两个操作数,进行乘法运算3*3=9,并把结果压入numStack栈中 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 计算完成后,因-(减法)+(加法)的优先级相同,栈内优先 。此时,把+optStack栈中弹出,并从numStack中相继弹出93 , 计算3+9=12,并把结果压入numStack栈中 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图