0772. Basic Calculator III
https://leetcode.com/problems/basic-calculator-iii
Description
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, '+'
, '-'
, '*'
, '/'
operators, and open '('
and closing parentheses ')'
. The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1]
.
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 = "6-4/2"
**Output:** 4
Example 3:
**Input:** s = "2*(5+5*2)/3+(6/2+8)"
**Output:** 21
Example 4:
**Input:** s = "(2+6*3+5-(3*14/7+2)*5)+3"
**Output:** -12
Example 5:
**Input:** s = "0"
**Output:** 0
Constraints:
1 <= s <= 104
s
consists of digits,'+'
,'-'
,'*'
,'/'
,'('
, and')'
.s
is a valid expression.
ac: Stack
class Solution {
public int calculate(String s) {
// Edge cases
if (s == null || s.length() == 0) return 0;
Deque<Character> operators = new ArrayDeque<>();
Deque<Integer> nums = new ArrayDeque<>();
int currNum = 0;
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 == '-' || c == '*' || c == '/') {
while (!operators.isEmpty() && canDoPreviousOperation(operators.peek(), c)) {
currNum = doOperation(nums.pop(), operators.pop(), currNum);
}
operators.push(c);
nums.push(currNum);
currNum = 0;
} else if (c == '(') {
operators.push('(');
} else if (c == ')') {
while (operators.peek() != '(') {
currNum = doOperation(nums.pop(), operators.pop(), currNum);
}
operators.pop(); // evict '('
}
}
while (!operators.isEmpty()) {
currNum = doOperation(nums.pop(), operators.pop(), currNum);
}
return currNum;
}
private int doOperation(int num1, Character operator, int num2) {
switch (operator) {
case '+': return num1 + num2;
case '-': return num1 - num2;
case '*': return num1 * num2;
case '/': return num1 / num2;
default:
throw new IllegalArgumentException("Invalid operator.");
}
}
private boolean canDoPreviousOperation(Character op1, Character op2) {
if (op1 == '(') return false;
if (op2 == '+' || op2 == '-') {
return true;
} else {
// op2 is * or /
if (op1 == '*' || op1 == '/') return true;
return false;
}
}
}
/*
E.g. ...(6 - 4 / 2)...
num1, op1, currNum, {currOp}, {num3} ...
1. currOp is +/-, or op1 && currOp both are * or /: currNum = eval(num1, op1, currNum)
2. other cases: currNum = eval(currNum, currOp, num3). Because we don't know whether it is left parenthesis or num3 after currOp, let's push currNum, currOp to stack and do calculation later.
stack operators: [-]
stack nums: [6]
*/
Last updated
Was this helpful?