阅读 340

用 js翻译翻译:什么叫tmd逆波兰式

1+1

A:别急着理解标题,先问你个问题。

A:1+1 是什么?

B:是 2 ?

A:不不不,我要说的不是这个,它由 1 + 1 组成。

B:这不是废话吗。

A:不不不,我说的是。

A:它由 1 + 1 组成。

A:而不是 + 1 1

A:也不是 1 1 +

B:你有病吗?

A:哈哈哈,这就引出了我们的标题,符合我们常理的 1+1 称为中缀表达式,符号在中间嘛。而 +11 是前缀表达式。

B: 我猜 11+ 是后缀表达式。

A:你他娘真是个人才。确实它是后缀表达式。也称为 逆波兰式。 (波兰逻辑学家J.Lukasiewicz提出的前缀表达式,后缀就成为逆波兰了

B:我去,绕这么大一圈.......

A:不扯淡了,进入正题吧。文章里我们就全称为后缀表达式了

后缀表达式

它是如何定义的呢?一个表达式的后缀式,符合以下四点

E 为常量或变量

如果E是一个常量或变量,那E的后缀式是它本身

比如,2 是 2 的后缀式。

E1 op E2 的形式

如果E是E1 op E2形式的表达式,这里op是任何二元操作符,则E的后缀式为E1'E2' op,这里E1'和E2'分别为E1和E2的后缀式。

这很好理解。

1+2 => 12+
1 => 1的后缀式
2 => 2的后缀式

加上括号的 E

如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式

这条也好理解。

1+1 的后缀式 与 (1+1) 的后缀式相同。

试试 中缀表达式 -> 后缀表达式

A:现在给你派一批任务,将中缀表达式转换为后缀表达式,你能完成吗。

B:SO EASY!

a + b

B: ab+

(a+b)/e

B: (a+b)e/
B: (a+b) 与 a+b 后缀式应该相同。那:ab+e/ B:最后是这个吧 ab+e/

(a+b)*c

B:跟上面差不多,ab+c*

(a+b)*c-(a+b)/e

B: 不就是把前两部放一块儿了吗,可以先用括号包起来 ((a+b)*c)-((a+b)/e),整体算一下 ((a+b)*c)((a+b)/e)-,括号内部再做转换

B:ab+c*ab+e/-

为什么需要后缀表达式

B: 这就完了吗。

A:完了,我说过了,很简单的。在构造后缀表达式的时候,只要考虑好运算符的优先级,就可万无一失

B:你整这么复杂干啥,中缀表达式看的挺爽,干嘛转成后缀呢?

A:嗯,中缀对于我们来说看的很爽,但对于代码实现来说,就很不爽了。

实现计算器

用户输入了一串表达式:(a+b)*c-(a+b)/e
快~快用代码实现计算下结果!
过去5s......
10s......
怎么还没算出来呀!什么!你不会!好吧好吧,因为要考虑到运算符优先级,这个难度确实高。

biubiubiu~

试试这个,直接按以下规则计算即可。

ab+c*ab+e/-

规则:

字符按顺序出 stack 栈,
如果是数字,则添加到 byte 栈里,
如果是符号,则拿 byte 的栈顶两项数字,进行运算,将运算结果入栈,直到 stack 为空

代码如下


const stack = [a, b,'+',c,'*',a,b,'+',e,'/','-']

function calculator(arr) {
  const op = ['+', '-', '*', '/']
  const byte = []
  while(arr.length) {
    let now = arr.shift()
    const index = op.indexOf(now)
    // 是符号
    if(index !== -1) {
      // 栈顶两元素
      const end = byte.pop(),
            first = byte.pop();
      switch(index){
        case 0:
          byte.push( first + end)
          break;
        case 1:
          byte.push( first - end)
          break;
        case 2:
          byte.push( first * end)
          break;
        case 3:
          byte.push( first / end)
          break;
      }
    // 不是符号
    } else {
      byte.push(now)
    }
  }
  console.log(byte)
}
复制代码

大概是这样的 a => b => +

可以累加了 a + b = r1

继续出

r1 => c => *

可以累乘了 r1 * c = r2

继续出

r2 => a => b => +

可以累加了 a + b = r3

继续出

r2 => r3 => e => /

可以 除法 了 r3 / e = r4

继续出
r2 => r4 => -

可以减法了

r2 - r4 = r5

花费 0.000000001 s,结果是 r5。

因为不考虑优先级,所以按照顺序计算,就可以把后缀表达式计算完成。不仅代码写起来快,运行的也快~这就是为什么把中缀转为后缀的原因。

后/前缀表达式语言 LISP

既然后/前缀表达式的执行效率高,那有没有后/前缀编程语言呢?

当然有。比如 LISP 语言

先简单的看看它的代码:

(setq a 10)
(setq b 20)
(format t "~% A + B = ~d" (+ a b))
(format t "~% A - B = ~d" (- a b))
(format t "~% A x B = ~d" (* a b))
(format t "~% B / A = ~d" (/ b a))
(format t "~% Increment A by 3 = ~d" (incf a 3))
(format t "~% Decrement A by 4 = ~d" (decf a 4))
复制代码

输出

A + B = 30
A - B = -10
A x B = 200
B / A = 2
Increment A by 3 = 13
Decrement A by 4 = 9

//原文出自【易百教程】,商业转载请联系作者获得授权,非商业请保留原文链接:https://www.yiibai.com/lisp/lisp_operators.html
复制代码

本文不是来推崇 lisp 的,你可以点击这篇文章了解更多: 上帝的lisp

中缀转后缀

B:emmm,后缀简单是简单,但写起来也太反人类了

A: 对呀,所以现代编程语言在计算机运算和代码可编写性上做了取舍,我们也不需要人肉换算逆波兰式了。不过,我们可以用代码先从中缀转后缀,再计算后缀表达式,来实现简单的计算器。

A:首先,我们得实现中缀转后缀,逻辑是这样的:

  • 首先构造 S1 运算符栈,和 S2 结果栈。中缀表达式 str 栈
  • str 按运算顺序从左到右出栈。
    • 当字符为数字时,直接压栈 S2
    • 当字符为运算符时
      • 如果 S1 栈顶元素优先级高于当前字符,则将 S1 栈顶元素出栈,并压栈 S2,直到 S1 栈顶元素优先级低于当前字符。最后,将当前字符压栈 S1
      • 如果 S1 栈顶元素优先级低于当前字符,则当前字符压栈 S1
    • 当字符为 ( 时,直接压栈,之后字符按照以上规则压栈。
    • 当字符为 )时,取与最近的 ( 中间的运算符,重复以上步骤
  • 当 str 栈空,依次出 S1 的栈

用 javascript 实现它


function calculator(str) {
  let n = 0, charStack = [], numStack = [], reducerStr =  [], leftIndex = -1
  const op = {
    '+' : 1,
    '-' : 1,
    '*' : 2,
    '/' : 2,
    '(' : 3,
    ')' : 3
  }
  while(n < str.length) {
    const byte = str[n]
    // 数字
    if(/\d/.test(byte)) {
      reducerStr.push(byte)
    } else if(/\(|\)/.test(byte)) {
      // 左括号入栈
      if(byte === '(') {
        charStack.push(byte)
        leftIndex = n
        console.log('左括号', byte)
      // 右括号出栈
      } else {
        let nowChar = charStack.pop()
        while(nowChar && nowChar !== '(') {
          reducerStr.push(nowChar)
          nowChar = charStack.pop()
        }
      }
    // 符号
    } else {
      // 字符栈顶元素
      let nowChar = charStack[charStack.length - 1]
      while(nowChar && op[byte] < op[nowChar] && nowChar !== '(') {
        charStack.pop()
        reducerStr.push(nowChar)
        nowChar = charStack[charStack.length - 1]
      }
      charStack.push(byte)
    }
    n++
  }
  while(charStack.length) {
    reducerStr.push(charStack.pop())
  }
  return reducerStr.join('')
}
复制代码

过程可视化

便于理解,我写了一个简单的 demo ,让转换过程可视化。你可以戳以下链接去感受一下。

可视化理解转换过程

我们实现了中缀转后缀,又实现了后缀表达式的计算,剩余的工作就是将这二者结合起来。这里就不演示了。

关注下面的标签,发现更多相似文章
评论