计算后缀表达式(逆波兰表达式)

计算后缀表达式

计算后缀表达式,又叫逆波兰表达式。我们一般看到的数学表达式就是中缀表达式,也就是将符号放在两个数字之间,例如: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", "*"]);

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

 

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 计算后缀表达式(逆波兰表达式)

赞 (2) 打赏

评论 0

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏