表达式题库

逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

示例1:

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例2:

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

思路:

:::details 点击查看代码

function evalRPN(tokens){
    const n=tokens.length;
    const stack=new Array(Math.floor((n+1)/2)).fill(0)
    let index=-1;
    for(let i=0;i<n;i++){
        const token=tokens[i];
        if(token=='+'){
            index--;
            stack[index]+=stack[index+1];
        }else if(token=='-'){
            index--;
            stack[index]-=stack[index+1];
        }else if(token=='*'){
            index--;
            stack[index]*=stack[index+1];
        }else if(token=='/'){
            index--;
            stack[index]=stack[index]/stack[index+1]>0?Math.floor(stack[index]/stack[index+1]):Math.ceil(stack[index]/stack[index+1])
        }else{
            index++;
            stack[index]=parseInt(token);
        }
    }
    return stack[index];
}

:::

性能分析:

• 时间复杂度：O(n)，其中 n 是数组 tokens 的长度。需要遍历数组 tokens 一次，计算逆波兰表达式的值。
• 空间复杂度：O(n)，其中 n 是数组 tokens 的长度。需要创建长度为 (n+1)/2 的数组模拟栈操作。