计算后缀表达式（逆波兰表达式）

计算后缀表达式 #

计算后缀表达式，又叫逆波兰表达式。我们一般看到的数学表达式就是中缀表达式，也就是将符号放在两个数字之间，例如：a+b

后缀表达式也就是将运算符放在相应数字的后面，例如：a b +

后缀表达式相当于树中的后序遍历。

示例 #

 ["2", "1", "+", "3", "*"] ->  ((2 + 1) *3) -> 9
 ["2", "1", "3", "*", "+"] ->  ( 2 + (1* 3)) -> 5
 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

如上处理下后缀表达式，仔细观察，你会发现后缀表达式实际上包含了优先级

Just Try #

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

参考答案 #

基于堆栈的解法 #

都怪自己偷偷看了一下打开，先入为主了。首先了解下栈是一种先入后出，后入先出的数据结构。本例非常适合用栈来解决。

做法就是，依次把数据压入栈，遇到操作符就把之前的2个数字出栈，做运算，然后入栈，这样到结束

function isOperator(c){
  return c=="+"|| c=="-" || c=="*"
}
function doOper(c, b, a){
  switch(c){
    case "+": return a+b;break;
    case "-": return a-b;break;
    case "*": return a*b;break;
  }
}
function algorithm(arr){
  let stack = [];
  arr.forEach(item=>{
    if(isOperator(item)){
      let a = stack.pop()
      let b = stack.pop()
      stack.push(doOper(item, +a, +b))
    }else{
      stack.push(item)
    }
  })
  return stack
}
function main(param) {
  console.show("参数：" + param, "结果：" + JSON.stringify(algorithm(param)))
  testPerformance(algorithm, param)
}
main(["2", "1", "3", "*", "+"]);
main(["2", "1", "+", "3", "*"]);

请你自动动手试一下：在线编程环境