224. Basic Calculator
給定一個表示有效表達式的字串 s，實現一個基本的計算器來計算並返回該表達式的結果。
注意：你不允許使用任何內建函數來將字串作為數學表達式進行計算，例如 eval()。
範例 1:
輸入: s = "1 + 1" 輸出: 2
Python
class Solution:
def calculate(self, s: str) -> int:
def calc(it):
stack = []
num = 0
op = '+'
while it < len(s):
if s[it].isdigit():
num = num * 10 + int(s[it])
elif s[it] in '+-*/':
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
elif op == '/':
stack.append(int(stack.pop() / num))
num = 0
op = s[it]
elif s[it] == '(':
num, it = calc(it + 1)
elif s[it] == ')':
break
it += 1
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
elif op == '/':
stack.append(int(stack.pop() / num))
return sum(stack), it
return calc(0)[0]
18.26MB, 18ms
C++
#include <string>
#include <stack>
#include <cctype>
class Solution {
public:
int calculate(string s) {
return calc(s, 0).first;
}
private:
std::pair<int, int> calc(const string& s, int i) {
std::stack<int> stack;
int num = 0;
char op = '+';
while (i < s.length()) {
if (std::isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
} else if (s[i] == '(') {
auto [res, next_i] = calc(s, i + 1);
num = res;
i = next_i;
} else if (s[i] == ')') {
updateStack(stack, op, num);
return {getResult(stack), i};
} else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
updateStack(stack, op, num);
op = s[i];
num = 0;
}
i++;
}
updateStack(stack, op, num);
return {getResult(stack), i};
}
void updateStack(std::stack<int>& stack, char op, int num) {
if (op == '+') stack.push(num);
else if (op == '-') stack.push(-num);
else if (op == '*') {
int top = stack.top();
stack.pop();
stack.push(top * num);
} else if (op == '/') {
int top = stack.top();
stack.pop();
stack.push(top / num);
}
}
int getResult(std::stack<int>& stack) {
int result = 0;
while (!stack.empty()) {
result += stack.top();
stack.pop();
}
return result;
}
};
15.19MB, 16ms
Javascript
/**
* @param {string} s
* @return {number}
*/
var calculate = function(s) {
const stack = [];
let num = 0;
let sign = 1;
let result = 0;
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (char >= '0' && char <= '9') {
num = num * 10 + (char - '0');
} else if (char === '+' || char === '-') {
result += sign * num;
num = 0;
sign = char === '+' ? 1 : -1;
} else if (char === '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (char === ')') {
result += sign * num;
result *= stack.pop(); // Get the sign before the parenthesis
result += stack.pop(); // Add the result before the parenthesis
num = 0;
}
}
if (num !== 0) result += sign * num;
return result;
};
54.34MB, 56ms
