简单表达式求值算法

1. 简单表达式求值算法

1. 作用:

1. 求特殊表达式的值
   1. 特殊性:
      1. 数字都为一位整数
      2. 没有括号运算符

2. 实际算法梗概:

算法主要使用两个栈:

1. 运算数栈,以下简称数栈
   1. 顺序存放运算数, 供运算符使用
2. 运算符栈,以下简称符栈
   1. 顺序存放运算符(栈顶优先度>栈底优先度)
3. 开始先无条件读取数字并压栈, 直到读取字符并压栈
4. 持续读取数字和字符并进行压栈
5. 试图叠罗汉一样把符栈叠得优先度越来越高
6. 直到读取到不能再叠下去的运算符(即优先度小于符栈栈顶)
7. 依次在数栈栈顶中取两个数与符栈栈顶一个字符进行结合
8. 结合后的数压栈到数栈
9. 类似消消乐, 直到符栈全部处理完(为空), 数栈只剩一个数(前面所有的数合并为一个数)
10. 继续读取
11. 继续叠罗汉
12. 继续消消乐
13. 直到读取完整个表达式
14. 返回最后数栈仅剩的那个数

3. 从具体实例描述实际算法过程:

计算A/B^C+D*E

1. 读A, 压入数栈
2. 读/, 压入符栈
3. 读B, 压入数栈
4. 读^, 优先度高于/, 压入符栈
5. 读C, 压入数栈
6. 读+
   1. 此时数栈和符栈的情况:
      1. 数栈: 栈顶→[C,B,A]
      2. 符栈: 栈顶→[^,/]
   2. 优先度低于符栈栈顶, 即^
      1. 从符栈顶取一个运算符, 即^
      2. 从数栈顶取两个数, 即C和B
      3. 结合B^C 为新的数T(1), 压入数栈
   3. 此时数栈和符栈的情况:
      1. 数栈: 栈顶→[T(1),A]
      2. 符栈: 栈顶→[/]
   4. 优先度低于符栈栈顶, 即/
      1. 从符栈顶取一个运算符, 即/
      2. 从数栈顶取两个数, 即T(1)和A
      3. 结合A/T(1) 为新的数T(2), 压入数栈
   5. 此时符栈为空
      1. 此时数栈和符栈的情况:
         1. 数栈: 栈顶→[T(2)]
         2. 符栈: 栈顶→[]
   6. +入符栈
7. 读D, 压入数栈
8. 读*, 优先度高于+, 压入符栈
9. 读D, 压入数栈
10. 此时数栈和符栈的情况:
    1. 数栈: 栈顶→[E,D,T(2)]
    2. 符栈: 栈顶→[*,+]
11. 此时表达式全部读完
    1. 从符栈顶取一个运算符, 即*
    2. 从数栈顶取两个数, 即E和D
    3. 结合D*E 为新的数T(3), 压入数栈

    4. ---

       1. 此时数栈和符栈的情况:
          1. 数栈: 栈顶→[T(3),T(2)]
          2. 符栈: 栈顶→[+]
    5. 从符栈顶取一个运算符, 即+
    6. 从数栈顶取两个数, 即T(3)和T(2)
    7. 结合T(2)*T(3) 为新的数T(4), 压入数栈

    8. ---

       1. 此时数栈和符栈的情况:
          1. 数栈: 栈顶→[T(4)]
          2. 符栈: 栈顶→[]
    9. 此时符栈为空
    10. 把数栈中唯一的T(4)返回