力扣刷题?【150. 逆波兰表达式求值】-一一网

这是我参与8月更文挑战的第 11 天，活动详情查看：8月更文挑战

题目链接

150. 逆波兰表达式求值

题目描述

根据逆波兰表示法，求表达式的值。

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

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

测试用例

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

必要知识点

平时我们习惯将表达式写成 (1 + 2) * (3 + 4)，加减乘除等运算符写在中间，因此称呼为中缀表达式。

而波兰表达式的写法为 (* (+ 1 2) (+ 3 4))，将运算符写在前面，因而也称为前缀表达式。

逆波兰表达式的写法为 ((1 2 +) (3 4 +) *)，将运算符写在后面，因而也称为后缀表达式。

对于波兰表达式和逆波兰表达式，去掉括号并不会影响优先级的计算

逆波兰表达式的计算方式：

需要使用一个栈 stack 来辅助计算

从头开始遍历测试用例的每一个字符串，如果当前的字符是数字，就压入 stack；如果当前的字符不是数字（即为运算符），就需要从 stack 中执行两次弹出操作，分别得到数字为 a, b，然后将b 操作符 a 的结果压入 stack。遍历完成字符串后，stack 中只会剩下唯一的一个数字，即是运算结果

题目分析

没啥好说的，按标准的逆波兰表示式的计算方式直接干他，碰到符号的话，就用 switch 选择对应的符号进行运行，唯一的细节点就是，题目明确要求了，除法舍去小数部分

题目答案

var evalRPN = function(tokens) {
	let stack = [];
	let oprator = new Set(['+', '-', '*', '/']);
	tokens.forEach(n => {
		if (oprator.has(n)) {
			let a = stack.pop(),
				b = stack.pop(),
				c;
			switch (n) {
				case '+':
					c = b + a;
					break;
				case '-':
					c = b - a;
					break;
				case '*':
					c = b * a;
					break;
				case '/':
					c = parseInt(b / a);
					break;
				default:
					break;
			}
			stack.push(c);
		} else {
			stack.push(Number(n));
		}
	})
	return stack.pop();
};
复制代码

小小优化一把

代码看着逻辑非常的清晰，就是有点，emmm，看着不太优雅的亚子

图片.png

复盘一下，就是这个 switch 看着太罗嗦了，那就直接给他改成 js 的 Objec，那么他的 key 嘛，那就是 4 款操作符咯

var evalRPN = function(tokens) {
    let caculate = {
        '+': (b, a) => a + b,
        '-': (b, a) => a - b,
        '*': (b, a) => a * b,
        '/': (b, a) => parseInt(a / b)
    }
    let stack = [];
    let oprators = new Set([...Object.keys(caculate)]);
    tokens.forEach(n => stack.push(oprators.has(n) ? caculate[n](stack.pop(), stack.pop()) : Number(n)));
    return stack.pop();
};
};
复制代码