• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int calculate(string s) {
stack<int> nums;  // stores nums
stack<char> ops;  // stores operators

for (int i = 0; i < s.length(); ++i) {
const char c = s[i];
if (isdigit(c)) {
int num = c - '0';
while (i + 1 < s.length() && isdigit(s[i + 1])) {
num = num * 10 + (s[i + 1] - '0');
++i;
}
nums.push(num);
} else if (c == '+' || c == '-' || c == '*' || c == '/') {
while (!ops.empty() && compare(ops.top(), c))
nums.push(calculate(pop(ops), pop(nums), pop(nums)));
ops.push(c);
}
}

while (!ops.empty())
nums.push(calculate(pop(ops), pop(nums), pop(nums)));

return nums.top();
}

private:
int calculate(char op, int b, int a) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
throw;
}

// return true if priority(op1) >= priority(op2)
bool compare(char op1, char op2) {
return op1 == '*' || op1 == '/' || op2 == '+' || op2 == '-';
}

char pop(stack<char>& ops) {
const char op = ops.top();
ops.pop();
return op;
}

int pop(stack<int>& nums) {
const int num = nums.top();
nums.pop();
return num;
}
};
``````

## JAVA

``````class Solution {
public int calculate(String s) {
Deque<Integer> nums = new ArrayDeque<>();  // stores nums
Deque<Character> ops = new ArrayDeque<>(); // stores operators and parentheses

for (int i = 0; i < s.length(); ++i) {
final char c = s.charAt(i);
if (Character.isDigit(c)) {
int num = c - '0';
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
num = num * 10 + (s.charAt(i + 1) - '0');
++i;
}
nums.push(num);
} else if (c == '+' || c == '-' || c == '*' || c == '/') {
while (!ops.isEmpty() && compare(ops.peek(), c))
nums.push(calculate(ops.pop(), nums.pop(), nums.pop()));
ops.push(c);
}
}

while (!ops.isEmpty())
nums.push(calculate(ops.pop(), nums.pop(), nums.pop()));

return nums.peek();
}

private int calculate(char op, int b, int a) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
throw new IllegalArgumentException();
}

// return true if priority(op1) >= priority(op2)
private boolean compare(char op1, char op2) {
return op1 == '*' || op1 == '/' || op2 == '+' || op2 == '-';
}
}
``````

## Python

``````class Solution:
def calculate(self, s: str) -> int:
ans = 0
prevNum = 0
currNum = 0
op = '+'

for i, c in enumerate(s):
if c.isdigit():
currNum = currNum * 10 + int(c)
if not c.isdigit() and c != ' ' or i == len(s) - 1:
if op == '+' or op == '-':
ans += prevNum
prevNum = currNum if op == '+' else -currNum
elif op == '*':
prevNum = prevNum * currNum
elif op == '/':
if prevNum < 0:
prevNum = ceil(prevNum / currNum)
else:
prevNum = prevNum // currNum
op = c
currNum = 0

return ans + prevNum
``````

• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
int calculate(string s) {
int ans = 0;
int prevNum = 0;
int currNum = 0;
char op = '+';

for (int i = 0; i < s.length(); ++i) {
const char c = s[i];
if (isdigit(c))
currNum = currNum * 10 + (c - '0');
if (!isdigit(c) && !isspace(c) || i == s.length() - 1) {
if (op == '+' || op == '-') {
ans += prevNum;
prevNum = op == '+' ? currNum : -currNum;
} else if (op == '*') {
prevNum *= currNum;
} else if (op == '/') {
prevNum /= currNum;
}
op = c;
currNum = 0;
}
}

return ans + prevNum;
}
};
``````

## JAVA

``````class Solution {
public int calculate(String s) {
int ans = 0;
int currNum = 0;
int prevNum = 0;
char op = '+';

for (int i = 0; i < s.length(); ++i) {
final char c = s.charAt(i);
if (Character.isDigit(c))
currNum = currNum * 10 + (c - '0');
if (!Character.isDigit(c) && c != ' ' || i == s.length() - 1) {
if (op == '+' || op == '-') {
ans += prevNum;
prevNum = op == '+' ? currNum : -currNum;
} else if (op == '*') {
prevNum *= currNum;
} else if (op == '/') {
prevNum /= currNum;
}
op = c;
currNum = 0;
}
}

return ans + prevNum;
}
}
``````

## Python

``````class Solution:
def calculate(self, s: str) -> int:
ans = 0
prevNum = 0
currNum = 0
op = '+'

for i, c in enumerate(s):
if c.isdigit():
currNum = currNum * 10 + int(c)
if not c.isdigit() and c != ' ' or i == len(s) - 1:
if op == '+' or op == '-':
ans += prevNum
prevNum = (currNum if op == '+' else -currNum)
elif op == '*':
prevNum *= currNum
elif op == '/':
prevNum = int(prevNum / currNum)
op = c
currNum = 0

return ans + prevNum
``````