Basic Calculator
Problem Highlights
- 🔗 Leetcode Link: https://leetcode.com/problems/basic-calculator/
- 💡 Problem Difficulty: Medium
- ⏰ Time to complete: 20 mins
- 🛠️ Topics: String
- 🗒️ Similar Questions: Evaluate Reverse Polish Notation, Basic Calculator II
1: U-nderstand
Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
Be sure that you clarify the input and output parameters of the problem:
- Does space affect the evaluation of an input expression?
- Spaces do not affect the evaluation of the input expression
- Does the input contain valid strings?
- Input always contains valid strings
Run through a set of example cases:
HAPPY CASE
Example 1:
Input: s = "1 + 1"
Output: 2
Example 2:
Input: s = " 2-1 + 2 "
Output: 3
EDGE CASE
Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
2: M-atch
Match
For this string problem, we can think about the following techniques:
-
Sort If the given string is given in a proper order, the string can be sorted in a specified arrangement.
-
Two pointer solutions (left and right pointer variables) A two pointer solution would be used if you are searching pairs in a sorted array.
-
Storing the elements of the array in a HashMap or a Set A hashmap will allow us to store object and retrieve it in constant time, provided we know the key.
-
Traversing the array with a sliding window Using a sliding window is iterable and ordered and is normally used for a longest, shortest or optimal sequence that satisfies a given condition.
-
Stack A stack is the natural fit for nested expressions: when we reach a
(we save the running result and pending sign onto stacks, and when we reach a)we pop them back to combine with the inner result. None of the techniques above handle this nesting — the stack approach is what both implementations below use.
3: P-lan
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Whenever we see a (, put the intermediate result into the stack, and start new calculation right after this (. When we see a ), pop the add/minus the result with the last item in the stack.
1. Iterate the expression string in reverse order one character at a time.
2. Once we encounter a character which is not a digit, we push the operand onto the stack. When we encounter an opening parenthesis (, this means an expression just ended.
3. Push the other non-digits onto to the stack.
4. Do this until we get the final result.
⚠️ Common Mistakes
- A tricky aspect of this problem includes handling a unary operator, such as “-3+3”, “4+(-5)”. For example, consider 12-3+(4-(5+6)) and what happens to array:
We start with [0], the current sum of the top level being zero.
The two ) push one zero each so we’re at [0, 0, 0].
The 6 gets pushed: [0, 0, 0, 6]
The + adds the 6 to the parent level: [0, 0, 6]
The 5 gets pushed: [0, 0, 6, 5]
The ( adds the 5 to the parent level: [0, 0, 11]. Note that this is the same as if the input were 12-3+(4-11) and we had just processed the 11. So we already fully processed that innermost parenthesis expression (5+6) correctly.
The - subtracts the 11 from the parent level: [0, -11].
The 4 gets pushed: [0, -11, 4]
The ( adds the 4 to the parent level: [0, -7].
The + adds the -7 to parent level: [-7].
The 3 gets pushed: [-7, 3]
The - subtracts the 3 from the parent level: [-10]
The 12 gets pushed: [-10, 12]
Now we have processed the whole input string and we have running sum -10 at the base level and the 12 hasn’t been incorporated yet. Just add them to get the final result -10+12=2.
4: I-mplement
Implement the code to solve the algorithm.
class Solution:
def calculate(self, s: str) -> int:
nums_stack = []
ops_stack =[]
cur_num = "0"
cur_op = "+"
running_result = 0
for i in range(len(s)):
c = s[i]
if c.isdigit():
cur_num += c
elif c in ["+", "-"]:
# before we replace cur_op, calculate previous num and put it into result
running_result += -1*int(cur_num) if cur_op == "-" else int(cur_num)
#refresh both
cur_num= "0"
cur_op = c
elif c == "(":
nums_stack.append(running_result)
ops_stack.append(cur_op)
running_result= 0
cur_op ="+"
cur_num = "0"
elif c == ")":
running_result += -1*int(cur_num) if cur_op == "-" else int(cur_num)
# take out previous context
prev_num = nums_stack.pop() if nums_stack else "0"
prev_op = ops_stack.pop() if ops_stack else "+"
# update the new result
if prev_op =="-":
running_result = -1*running_result
running_result = prev_num + running_result
#refresh the context
cur_num= "0"
cur_op ="+"
#left over
if cur_num: running_result += -1*(int(cur_num)) if cur_op =="-" else int(cur_num)
return running_result
public class Solution {
public int calculate(String s) {
Stack<Integer> numsStack = new Stack<>();
Stack<Character> opsStack = new Stack<>();
String curNum = "0";
char curOp = '+';
int runningResult = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
curNum += c;
}
else if (c == '+' || c == '-') {
runningResult += (curOp == '-') ? -Integer.parseInt(curNum) : Integer.parseInt(curNum);
curNum = "0";
curOp = c;
}
else if (c == '(') {
numsStack.push(runningResult);
opsStack.push(curOp);
runningResult = 0;
curOp = '+';
curNum = "0";
}
else if (c == ')') {
runningResult += (curOp == '-') ? -Integer.parseInt(curNum) : Integer.parseInt(curNum);
int prevNum = (!numsStack.isEmpty()) ? numsStack.pop() : 0;
char prevOp = (!opsStack.isEmpty()) ? opsStack.pop() : '+';
if (prevOp == '-') {
runningResult = -runningResult;
}
runningResult = prevNum + runningResult;
curNum = "0";
curOp = '+';
}
}
if (!curNum.equals("")) {
runningResult += (curOp == '-') ? -Integer.parseInt(curNum) : Integer.parseInt(curNum);
}
return runningResult;
}
}
5: R-eview
Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.
- Trace through your code with an input to check for the expected output
- Catch possible edge cases and off-by-one errors
6: E-valuate
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
- Time Complexity: O(N), where N is the length of the string
- Space Complexity: O(N) to account for stack used