且听疯吟 在此记录扯淡的青春
C# 中缀表达式计算

给出一个字符串的计算表达式如 1+2*(3-4)/5 ,不使用其他库如何计算其结果?
在脚本语言中这也许不算什么问题,但是在 C# 这样的静态语言中则需要我们自己来解析表达式实现计算。

中缀表达式

中缀表达式 (Infix Expression),即形如 a+b-c*d 这样的表达式。运算符位于两个操作数的中间,也是我们习惯的写法。但是这种写法对于计算机运算来说是不够效率的,每次计算表达式,都需要先分析整个表达式,然后根据优先级来逐步计算。

后缀表达式

后缀表达式 (Suffix Expression),也叫做逆波兰表达式,即将运算符记在操作数之后,如 a+b 记作 a b +。使用后缀表达式不需要关注运算符的优先级,计算机能够按表达式从左向右来计算,从而利用堆栈并提高计算效率。

表达式转换

既然后缀表达式有这些好处,那么如何将常见的中缀表达式转为后缀表达式?一般使用 调度场算法。实际上语法树的后序遍历也是后缀表示法。

简单分析下从中缀表达式到后缀表达式的过程:

  1. 定义两个栈 Operand(操作数栈)和 Operator(运算符栈);
  2. 从左到右遍历字符串,按如下规则:
    • 如果该字符为左括号,直接压入 Operator 栈中;
    • 如果该字符为右括号,则依次弹出 Operator 栈中的元素,并压入 Operand 栈中,直到遇到左括号为止。将左括号弹出,但是不压入栈;
    • 如果该字符是操作符:
      • 首先将临时变量中两操作符之间的字符取出,此处可以判断是否是数字,如果不是,则说明字符串不是标准的表达式;如果是,将其存入 Operand 栈中并清空临时变量;
      • 查看 Operator 栈中是否存在运算符:
        • 如不存在,将该操作符压入 Operator 栈中;
        • 如存在,判断栈顶元素是否是左括号,如果是,将运算符压入 Operator 栈中;否则,比较该操作符和 Operator 栈顶操作符的优先级:
          • 该操作符优先级较高,将该操作符压入 Operand栈中;
          • 该操作符优先级较低或相等,则弹出 Operator 栈顶元素,将其压入 Operand 中,然后循环执行比较和弹出操作,直到遇到左括号或 Operator 为空或栈顶操作符优先级低于该操作符,将该运算符压入 Operator 栈中;
    • 如果该字符不是操作符也不是括号,则将其存入临时变量;
  3. 循环完成,将临时变量(即最后一个数字)压入 Operand 栈中;
  4. 将 Operator 栈依次弹出并压入到 Operand 栈中;
  5. 将 Operand 栈按从底部到顶部读取,即可记作后缀表达式。

后缀表达式计算

  1. 将后缀表达式转换成堆栈 Suffix;
  2. 定义一个新的栈 Result;
  3. 依次弹出 Suffix 栈顶元素:
    • 如果该元素不是运算符,将其压入 Result 栈中;
    • 如果该元素是运算符,则弹出 Result 顶端两个元素(即 Pop 两次),将其作为左操作数和右操作数,按该运算符进行运算,将结果压入 Result 栈中;
  4. Result 栈顶元素即计算结果

这是简单的表达式计算方法,但是运用该原理,我们可以实现包含自定义函数的复杂计算。

Demo: