class Solution {
public:
int calculate(string s) {
}
};
227. 基本计算器 II
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "3+2*2" 输出：7
示例 2：
输入：s = " 3/2 " 输出：1
示例 3：
输入：s = " 3+5 / 2 " 输出：5
提示：
1 <= s.length <= 3 * 105s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开s 表示一个 有效表达式[0, 231 - 1] 内原站题解
c 解法, 执行用时: 4 ms, 内存消耗: 8.3 MB, 提交时间: 2023-09-07 10:45:38
int calculate(char* s) {
int n = strlen(s);
int stk[n], top = 0;
char preSign = '+';
int num = 0;
for (int i = 0; i < n; ++i) {
if (isdigit(s[i])) {
num = num * 10 + (int)(s[i] - '0');
}
if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
switch (preSign) {
case '+':
stk[top++] = num;
break;
case '-':
stk[top++] = -num;
break;
case '*':
stk[top - 1] *= num;
break;
default:
stk[top - 1] /= num;
}
preSign = s[i];
num = 0;
}
}
int ret = 0;
for (int i = 0; i < top; i++) {
ret += stk[i];
}
return ret;
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 12.3 MB, 提交时间: 2023-09-07 10:45:18
class Solution {
public:
int calculate(string s) {
vector<int> stk;
char preSign = '+';
int num = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
if (isdigit(s[i])) {
num = num * 10 + int(s[i] - '0');
}
if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
switch (preSign) {
case '+':
stk.push_back(num);
break;
case '-':
stk.push_back(-num);
break;
case '*':
stk.back() *= num;
break;
default:
stk.back() /= num;
}
preSign = s[i];
num = 0;
}
}
return accumulate(stk.begin(), stk.end(), 0);
}
};
java 解法, 执行用时: 18 ms, 内存消耗: 43.9 MB, 提交时间: 2023-09-07 10:45:00
class Solution {
public int calculate(String s) {
Deque<Integer> stack = new ArrayDeque<Integer>();
char preSign = '+';
int num = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
if (Character.isDigit(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
}
if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
switch (preSign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop() * num);
break;
default:
stack.push(stack.pop() / num);
}
preSign = s.charAt(i);
num = 0;
}
}
int ans = 0;
while (!stack.isEmpty()) {
ans += stack.pop();
}
return ans;
}
}
javascript 解法, 执行用时: 96 ms, 内存消耗: 50.2 MB, 提交时间: 2023-09-07 10:44:34
/**
* @param {string} s
* @return {number}
*/
var calculate = function(s) {
s = s.trim();
const stack = new Array();
let preSign = '+';
let num = 0;
const n = s.length;
for (let i = 0; i < n; ++i) {
if (!isNaN(Number(s[i])) && s[i] !== ' ') {
num = num * 10 + s[i].charCodeAt() - '0'.charCodeAt();
}
if (isNaN(Number(s[i])) || i === n - 1) {
switch (preSign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop() * num);
break;
default:
stack.push(stack.pop() / num | 0);
}
preSign = s[i];
num = 0;
}
}
let ans = 0;
while (stack.length) {
ans += stack.pop();
}
return ans;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 8.4 MB, 提交时间: 2023-09-07 10:44:12
func calculate(s string) (ans int) {
stack := []int{}
preSign := '+'
num := 0
for i, ch := range s {
isDigit := '0' <= ch && ch <= '9'
if isDigit {
num = num*10 + int(ch-'0')
}
if !isDigit && ch != ' ' || i == len(s)-1 {
switch preSign {
case '+':
stack = append(stack, num)
case '-':
stack = append(stack, -num)
case '*':
stack[len(stack)-1] *= num
default:
stack[len(stack)-1] /= num
}
preSign = ch
num = 0
}
}
for _, v := range stack {
ans += v
}
return
}
python3 解法, 执行用时: 148 ms, 内存消耗: 19.6 MB, 提交时间: 2023-09-07 10:43:41
# 用栈来处理
class Solution:
def calculate(self, s: str) -> int:
n = len(s)
stack = []
preSign = '+'
num = 0
for i in range(n):
if s[i] != ' ' and s[i].isdigit():
num = num * 10 + ord(s[i]) - ord('0')
if i == n - 1 or s[i] in '+-*/':
if preSign == '+':
stack.append(num)
elif preSign == '-':
stack.append(-num)
elif preSign == '*':
stack.append(stack.pop() * num)
else:
stack.append(int(stack.pop() / num))
preSign = s[i]
num = 0
return sum(stack)