https://leetcode.com/problems/basic-calculator
Description
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
**Input:** s = "1 + 1"
**Output:** 2
Example 2:
**Input:** s = " 2-1 + 2 "
**Output:** 3
Example 3:
**Input:** s = "(1+(4+5+2)-3)+(6+8)"
**Output:** 23
Constraints:
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
'+' is not used as a unary operation.
'-' could be used as a unary operation and in this case, it will not be used directly after a +ve or -ve signs (will be inside parentheses).
There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer.
ac1： Deque + multiple passes
slow
class Solution {
public int calculate(String s) {
Deque<String> deque = new ArrayDeque<String>();
// 1st pass, parentheses
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') continue;
if (c == '(' || c == '+' || c == '-') {
if (sb.length() > 0) deque.offer(sb.toString());
sb.setLength(0);
deque.offer(String.valueOf(c));
} else if (c == ')'){
if (sb.length() > 0) deque.offer(sb.toString());
sb.setLength(0);
Deque<String> sub = new ArrayDeque<String>();
while(!deque.peekLast().equals("(")) {
sub.offerFirst(deque.pollLast());
}
deque.pollLast();
deque.offer(calDeque(sub));
} else {
sb.append(c);
}
}
if (sb.length() > 0) deque.offer(sb.toString());
// 2nd pass, get result
return Integer.parseInt(calDeque(deque));
}
private String calDeque(Deque<String> d) {
int val = Integer.parseInt(d.poll());
while (!d.isEmpty()) {
String operator = d.poll();
int operand = Integer.parseInt(d.poll());
if (operator.equals("+")) {
val += operand;
} else if (operator.equals("-")) {
val -= operand;
}
}
return "" + val;
}
}
/**
Deque, 1st pass, handle parentheses
2nd pass, calculate
**/
ac2: stack
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<Integer>();
int res = 0;
int num = 0;
int sign = 1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (int) (c - '0');
} else if (c == '+') {
res += sign * num;
num = 0;
sign = 1;
} else if (c == '-') {
res += sign * num;
num = 0;
sign = -1;
} else if (c == '(') {
stack.push(res);
stack.push(sign);
res = 0;
sign = 1;
} else if (c == ')') {
res += sign * num;
res = stack.pop() * res + stack.pop();
num = 0;
sign = 1;
}
}
if (num != 0) res += sign * num;
return res;
}
}
ac3: 2 stack
more intuitive, generalize to complex problem like #227 #772
class Solution {
public int calculate(String s) {
Stack<Integer> nums = new Stack<>();
Stack<Character> ops = new Stack<>();
nums.push(0);
ops.push('+');
int n = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') continue;
if (Character.isDigit(c)) {
n = n * 10 + c - '0';
} else if (c == '(') {
ops.push(c);
} else if (c == '+' || c == '-') {
if (ops.peek() != '(') {
n = operate(nums.pop(), ops.pop(), n);
}
nums.push(n);
ops.push(c);
n = 0;
} else if (c == ')') {
while (ops.peek() != '(') n = operate(nums.pop(), ops.pop(), n);
ops.pop();
}
}
while (!ops.isEmpty()) n = operate(nums.pop(), ops.pop(), n);
return n;
}
private int operate(int val1, Character oper, int val2) {
if (oper == '+') return val1 + val2;
else return val1 - val2;
}
}
ac4: stack, get rid of parenthesis
sign = stack.peek() * (c == '+' ? 1: -1); is to simulate the process of removing parenthesis.
class Solution {
public int calculate(String s) {
Deque<Integer> stack = new ArrayDeque<>();
int prevVal = 0, currNum = 0;
int sign = 1; // 1 for +, -1 for -.
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') continue;
if (Character.isDigit(c)) {
currNum = currNum * 10 + (c - '0');
} else if (c == '+' || c == '-') {
prevVal += sign * currNum;
// Reset
sign = c == '+' ? 1 : -1;
currNum = 0;
} else if (c == '(') {
// Store the sate:
stack.push(prevVal);
stack.push(sign);
// Reset
prevVal = 0;
sign = 1;
} else if (c == ')') {
currNum = prevVal + sign * currNum;
// Retrieve what we stored
sign = stack.pop();
prevVal = stack.pop();
}
}
return prevVal + sign * currNum;
}
}
/*
O(N) time, O(N) space
num1, op1, num2, {op2} ...
When we meet op2, update num1 = eval(num1, op1, num2).
We keep state in (num1, op1), so push them to stack when meet new parenthesis.
*/