[LeetCode] 227. Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:
Input: “3+2*2”
Output: 7

Example 2:
Input: “ 3/2 “
Output: 1

Example 3:
Input: “ 3+5 / 2 “
Output: 5

Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.

基本计算器 II。

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/basic-calculator-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题意跟版本一基本一样，多了乘法和除法的操作但是省去了括号，同时需要跳过中间遇到的空格。有了乘法和除法的话，计算就需要有优先级。思路依然是用 stack，也是按字符遍历 input，遇到乘号和除号的时候需要把栈顶元素 pop 出来，先计算乘法/除法，把计算后的结果再放入栈内。如果遇到一个字符既不是数字也不是空格，那么一定是一个运算符。如果遇到的是加号或者减号，则把他变成栈顶元素的正号/负号；如果是乘号/除号的话则进行计算，把计算结果入栈。在这道题中，运算符号是不入栈的，最后从stack弹出元素的时候，所有元素之间做的只有加法。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
	public int calculate(String s) {
		Deque<Integer> stack = new ArrayDeque<>();
		int res = 0;
		char sign = '+';
		int num = 0;
		for (int i = 0; i < s.length(); i++) {
			if (Character.isDigit(s.charAt(i))) {
				num = s.charAt(i) - '0';
				while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
					num = num * 10 + s.charAt(i + 1) - '0';
					i++;
				}
			}
			// 不是数字，不是空格，又不是最后一个字符，那么只能是一个运算符号
			// 走到最后一个位置的时候需要特判，否则是不会被入栈的
			if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == s.length() - 1) {
				if (sign == '+') {
					stack.push(num);
				}
				if (sign == '-') {
					stack.push(-num);
				}
				if (sign == '*') {
					stack.push(stack.pop() * num);
				}
				if (sign == '/') {
					stack.push(stack.pop() / num);
				}
				sign = s.charAt(i);
				num = 0;
			}
		}

		for (int i : stack) {
			res += i;
		}
		return res;
	}
}

相关题目

224. Basic Calculator
227. Basic Calculator II
772. Basic Calculator III
1006. Clumsy Factorial