Basic Calculator - codepath/compsci_guides GitHub Wiki
- 🔗 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](https://leetcode.com/problems/basic-calculator-ii/
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: 23Match
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 are 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.
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.- 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.
Implement the code to solve the algorithm.
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_resultpublic 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;
}
}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
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