算数式计算

字符串算式先转为逆波兰式(后缀表达式)，然后计算；

一、求逆波兰表达式

核心思想：

逆波兰算法的核心思想是将普通的中缀表达式转换为后缀表达式。

什么是中缀表达式？
例如a+b，运算符在两个操作数的中间。这是我们从小学开始学习数学就一直使用的表达式形式。

什么是后缀表达式？
例如a b + ，运算符在两个操作数的后面。后缀表达式虽然看起来奇怪，不利于人阅读，但利于计算机处理。

转换为后缀表达式的好处是：

• 去除原来表达式中的括号，因为括号只指示运算顺序，不是实际参与计算的元素。
• 使得运算顺序有规律可寻，计算机能编写出代码完成计算。

核心步骤：

逆波兰算法的核心步骤就2个：

1. 将中缀表达式转换为后缀表达式，例如输入的原始表达式是 3(5+7) ，转换得到 3 5 7 +
2. 根据后缀表达式，按照特定的计算规则得到最终计算结果

具体步骤：

中缀表达式转换为后缀表达式：

1. 你需要设定一个栈SOP,和一个线性表 L 。SOP用于临时存储运算符和左括号分界符( ，L用于存储后缀表达式。
2. 遍历原始表达式中的每一个表达式元素：
   1. 如果是操作数，则直接追加到 L中。只有 运算符 或者 分界符（ 才可以存放到 栈SOP中；
   2. 如果是分界符：
      • 如果是左括号 ( ， 则 直接压入SOP，等待下一个最近的 右括号 与之配对。
      • 如果是右括号 ) ，则说明有一对括号已经配对(在表达式输入无误的情况下)。
        不将它压栈，丢弃它，然后从SOP中出栈，得到元素e，将e依次追加到L里。一直循环，直到出栈元素e 是 左括号 ( ，同样丢弃他。
   3. 如果是运算符（用op1表示）：
      • 如果SOP栈顶元素（用op2表示） 不是运算符，则二者没有可比性，则直接将此运算符op1压栈。 例如栈顶是左括号 ( ，或者栈为空。
      • 如果SOP栈顶元素（用op2表示） 是运算符 ，则比较op1和 op2的优先级。如果op1 > op2 ，则直接将此运算符op1压栈。
      • 如果不满足op1 > op2，则将op2出栈，并追加到L，再试图将op1压栈，如果如果依然不满足 op1>新的栈顶op2，继续将新的op2弹出追加到L ，直到op1可以压入栈中为止。
      • 也就是说，如果在SOP栈中，有2个相邻的元素都是运算符，则他们必须满足：下层运算符的优先级一定小于上层元素的优先级，才能相邻。
3. 最后，如果SOP中还有元素，则依次弹出追加到L后，就得到了后缀表达式。

举例：

中缀式子：

$$(2*(3-4))*5$$

逆波兰式（后缀式子）：

$$2 3 4-\*5\*$$

二、逆波兰表达式的计算

步骤：

1. 从左到右扫描表达式，如果当前字符为数字，则入栈。
2. 如果当前字符为运算符，则将栈顶两个元素出栈，作相应运算，结果再入栈。
3. 最后当表达式扫描完后，栈里的就是计算结果了。

赏

谢谢你请我喝可乐

支付宝

微信