计算器（面试题16.26）

题目

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例

输入: "3+2*2" 输出: 7

输入: " 3/2 " 输出: 1

输入: " 3+5 / 2 " 输出: 5

说明

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

算法

使用dig保存上一个符号，使用cur保存当前的数字，使用stack来保存暂时的结果

• 遍历字符串
  • 如果遇到空格" "，跳过
  • 如果遇到数字，拼接在cur后面
  • 如果遇到标点，则：
    • 是加号+，则将cur转换为数字后推入stack
    • 是减号-，则将cur转换为负数后推入stack
    • 是乘号*，则将stack中最后一项弹出，和cur转换数字后相乘，推入stack
    • 是除号/，则将stack中最后一项弹出，和cur转换数字后相除，推入stack
• 将cur重置为空字符串" "，用来保存下一个数字
• 将当前的符号保存在dig中，供下一个数字做判断
• 最后将stack中所有项相加得到的结果就是所求

因为运算先后顺序，*、/先做运算，所以我们在上一个符号是乘除时（因为我们没遇到一个符号时，说明这个数字结束了，当前数字运算要看前一个符号和前一个数字），将上一个数字从栈中拿出做运算，并将结果推入栈；如果上一个符号是减号，则将数字取反推入栈，因为我们结果是要对栈中所有数字求和得结果，所以减去一个数转换成加这个数的负数；如果上一个符号是加号，则直接推入栈中即可

我们遍历的时候要遍历到s[s.length]的位置，这是为了将最后一个数字能推入栈中

最后栈中保存的是需要加的数、需要减去的数的相反数、乘除法运算后的结果，我们将这些值加起来就能得到结果了

export const calculate = (s) => {
	let dig = "+",
		cur = "";
	const stack = [];
	for (let i = 0; i <= s.length; i++) {
		if (s[i] === " ") continue;
		if (s[i] <= "9" && s[i] >= "0") {
			cur += s[i];
			continue;
		}
		if (dig === "+") stack.push(Number(cur));
		else if (dig === "-") stack.push(-Number(cur));
		else if (dig === "*") stack.push(stack.pop() * Number(cur));
		else if (dig === "/") stack.push(~~(stack.pop() / Number(cur)));
		cur = "";
		dig = s[i];
	}
	return stack.reduce((acc, cur) => (acc += cur));
};