计算后缀表达式
计算后缀表达式,又叫逆波兰表达式。我们一般看到的数学表达式就是中缀表达式,也就是将符号放在两个数字之间,例如: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国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 计算后缀表达式(逆波兰表达式)