# [LeetCode] 224. Basic Calculator 基本计算器

2021年09月15日 阅读数：1

Implement a basic calculator to evaluate a simple expression string.html

The expression string may contain open `(` and closing parentheses `)`, the plus `+` or minus sign `-`non-negative integers and empty spaces .java

You may assume that the given expression is always valid.python

Some examples:git

```"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23```

Note: Do not use the `eval` built-in library function.express

Java:app

```public int calculate(String s) {
// delte white spaces
s = s.replaceAll(" ", "");

Stack<String> stack = new Stack<String>();
char[] arr = s.toCharArray();

StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == ' ')
continue;

if (arr[i] >= '0' && arr[i] <= '9') {
sb.append(arr[i]);

if (i == arr.length - 1) {
stack.push(sb.toString());
}
} else {
if (sb.length() > 0) {
stack.push(sb.toString());
sb = new StringBuilder();
}

if (arr[i] != ')') {
stack.push(new String(new char[] { arr[i] }));
} else {
// when meet ')', pop and calculate
ArrayList<String> t = new ArrayList<String>();
while (!stack.isEmpty()) {
String top = stack.pop();
if (top.equals("(")) {
break;
} else {
}
}

int temp = 0;
if (t.size() == 1) {
temp = Integer.valueOf(t.get(0));
} else {
for (int j = t.size() - 1; j > 0; j = j - 2) {
if (t.get(j - 1).equals("-")) {
temp += 0 - Integer.valueOf(t.get(j));
} else {
temp += Integer.valueOf(t.get(j));
}
}
temp += Integer.valueOf(t.get(0));
}
stack.push(String.valueOf(temp));
}
}
}

ArrayList<String> t = new ArrayList<String>();
while (!stack.isEmpty()) {
String elem = stack.pop();
}

int temp = 0;
for (int i = t.size() - 1; i > 0; i = i - 2) {
if (t.get(i - 1).equals("-")) {
temp += 0 - Integer.valueOf(t.get(i));
} else {
temp += Integer.valueOf(t.get(i));
}
}
temp += Integer.valueOf(t.get(0));

return temp;
}　　```

Python:post

```class Solution:
# @param {string} s
# @return {integer}
def calculate(self, s):
operands, operators = [], []
operand = ""
for i in reversed(xrange(len(s))):
if s[i].isdigit():
operand += s[i]
if i == 0  or not s[i-1].isdigit():
operands.append(int(operand[::-1]))
operand = ""
elif s[i] == ')' or s[i] == '+' or s[i] == '-':
operators.append(s[i])
elif s[i] == '(':
while operators[-1] != ')':
self.compute(operands, operators)
operators.pop()

while operators:
self.compute(operands, operators)

return operands[-1]

def compute(self, operands, operators):
left, right = operands.pop(), operands.pop()
op = operators.pop()
if op == '+':
operands.append(left + right)
elif op == '-':
operands.append(left - right)
```

C++:ui

```class Solution {
public:
int calculate(string s) {
int res = 0, sign = 1, n = s.size();
stack<int> st;
for (int i = 0; i < n; ++i) {
char c = s[i];
if (c >= '0') {
int num = 0;
while (i < n && s[i] >= '0') {
num = 10 * num + s[i++] - '0';
}
res += sign * num;
--i;
} else if (c == '+') {
sign = 1;
} else if (c == '-') {
sign = -1;
} else if (c == '(') {
st.push(res);
st.push(sign);
res = 0;
sign = 1;
} else if (c == ')') {
res *= st.top(); st.pop();
res += st.top(); st.pop();
}
}
return res;
}
};　　```

C++:lua

```class Solution2 {
public:
int calculate(string s) {
stack<int> operands;
stack<char> operators;
string operand;
for (int i = s.length() - 1; i >= 0; --i) {
if (isdigit(s[i])) {
operand.push_back(s[i]);
if (i == 0 || !isdigit(s[i - 1])) {
reverse(operand.begin(), operand.end());
operands.emplace(stoi(operand));
operand.clear();
}
} else if (s[i] == ')' || s[i] == '+' || s[i] == '-') {
operators.emplace(s[i]);
} else if (s[i] == '(') {
while (operators.top() != ')') {
compute(operands, operators);
}
operators.pop();
}
}
while (!operators.empty()) {
compute(operands, operators);
}
return operands.top();
}

void compute(stack<int>& operands, stack<char>& operators) {
const int left = operands.top();
operands.pop();
const int right = operands.top();
operands.pop();
const char op = operators.top();
operators.pop();
if (op == '+') {
operands.emplace(left + right);
} else if (op == '-') {
operands.emplace(left - right);
}
}
};
```

[LeetCode] 227. Basic Calculator II 基本计算器 II