## # 224. Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

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

Example 1:

``````Input: "1 + 1"
Output: 2
``````

Example 2:

``````Input: " 2-1 + 2 "
Output: 3
``````

Example 3:

``````Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
``````

Note:

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

### # Solution

Approach 1: Stack for everything.

Approach 2: Stack for signs.

Approach 3: general solution is to build postfix notation and evaluate.

### # Code (Python)

Approach 1:

``````import re

class Solution:
def calculate(self, expr: str) -> int:
# trick: wrap the original expression with a bracket to cut corner cases
tokens = ['('] + self._tokenize(expr) + [')']
if not tokens:
return 0

stack = []
for token in tokens:
if token != ')':
stack.append(token)
else:
temp_result = 0
while len(stack) and stack[-1] != '(':
num = int(stack.pop())
op = stack.pop()
if op == '(':
temp_result += num
stack.append(temp_result)
break
else:
temp_result += num if op == '+' else -num
# this handles cases like 1-(-2)
if stack[-1] == '(':
stack.pop()
stack.append(temp_result)
return stack[0]

def _tokenize(self, expression):
return [e for e in re.split('(\D)', expression) if e and not re.match('\s', e)]
``````

Approach 3:

``````class Solution:
def calculate(self, s: str) -> int:
# idea for all calculators: convert to postfix notation, then evalutate
# example of postfix: (a+b)*c - (a+b)/d => [a, b, +, c, *, a, b, + d, /, -]
# this following solution work for all operators in +-*/
return self._evaluate(self._to_postfix(s))

def _to_postfix(self, expression):
# two stacks: a stack (list) storing postfix, and an operator stack to store operators and left paren
# operators have priorities: +- has priority 1, */ has priority 2
postfix = []
operators = []
value = '' # to handle multiple digits
ops = {
'+': 1,
'-': 1,
'*': 2,
'/': 2
}

for char in expression:
if not char or char == ' ':
continue
if char.isdigit():
value += char
else:
if value:
postfix.append(int(value))
value = ''
if char == '(':
operators.append(char)
elif char in ops:
# pop from operators with higher or equal priority, or until meet a (, then push char onto operators
while operators and operators[-1] != '(' and ops[operators[-1]] >= ops[char]:
postfix.append(operators.pop())
operators.append(char)
else: # )
# pop from operators until meet a (
while operators and operators[-1] != '(':
postfix.append(operators.pop())
operators.pop()
# pop remaining digits first
if value:
postfix.append(int(value))
# pop remaining operators
while operators:
postfix.append(operators.pop())

return postfix

def _evaluate(self, postfix):
ops = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: a / b
}
current = []
for item in postfix:
if item in ops:
val2, val1 = current.pop(), current.pop()
current.append(ops[item](val1, val2))
else:
current.append(item)
return current[0]
``````

### # Code (C++)

Approach 1:

``````// Stack for everything.
class Solution {
public:
int calculate(string s) {
stack<string> st;
st.push("(");
int head = 0;
for (int i = 0; i <= s.size(); ++i)
{
if (i == s.size() || !isdigit(s[i]))
{
if (i > head)
{
}
if (i == s.size() || s[i] == ')')
{
int total = stoi(st.top());
st.pop();
if (st.top() == "-")
total = 0 - total;
while (!st.empty() && st.top() != "(")
{
st.pop(); // pop "+" or "-".
int num = stoi(st.top());
st.pop();
if (st.top() == "-")
num = 0 - num;
total += num;
}
st.pop(); // pop "(".
st.push(std::to_string(total));
}
else if (i < s.size() && s[i] != ' ')
{
st.push(string(1, s[i]));
}
head = i + 1;
}
}
return stoi(st.top());
}
};
``````

Approach 2:

``````// Stack for signs.
class Solution {
public:
int calculate(string s) {
stack<int> stSign;
stSign.push(1);
int res = 0;
int sign = 1;
int head = 0;
for (int i = 0; i <= s.size(); ++i)
{
if (i == s.size() || !isdigit(s[i]))
{
if (i > head)
{
res += sign * stoi(s.substr(head, i - head));
}
if (i < s.size())
{
if (s[i] == '+')
sign = stSign.top();
else if (s[i] == '-')
sign = 0 - stSign.top();
else if (s[i] == '(')
stSign.push(sign);
else if (s[i] == ')')
stSign.pop();
}
head = i + 1;
}
}
return res;
}
};
``````