Leetcode 224. Basic Calculator
Problem Explanation
We need to build a basic calculator which will evaluate a given expression string. This string might contain parentheses "()" , plus "+" or minus "-" signs , non-negative integers and empty spaces " " . The given expression will always be valid and eval built-in library function will not be used to solve the problem. The function will then return the calculated value of the expression.
For example, if the input is "1 + 1", the output will be 2. If the input is "(1+(4+5+2)-3)+(6+8)", the output will be 23.
Approach
To approach this problem, we will use the concept of Stack data structure and evaluate the expression. We will have a variable 'sign' which will hold the value of the current sign and if we encounter a sign, we will add the current number and num
to the answer
. num
will always store the latest number. So if the current character is a digit, we will update num. If the character is
(, we will push the current
signin the stack. If the character is
), we will pop the stack and if the character is
+or
- we will add
sign*numto
ans, update the
sign, reset
num, update
signas top of stack * current
sign(
+is 1 and
-` is -1)
Let's understand it with an example
For example "2-1 + 2"
Here we start with initial values ans=0
and num=0
and sign=1
. We start our scanning from the left.
So, the first digit is 2, so num=2
. The next digit we encounter is "-", so we add sign*num
to ans
i.e 2
to the ans
so ans=2
, we encountered a -
so sign = -1 * 1 = -1
, then we see a 1
hence num=1
, the next character we see is +
so ans = ans + sign*num = 2 - 1 = 1
, we encountered a +
so sign = 1 * 1 = 1
, we see a 2
so num=2
. Finally when we reach the end ans = ans + sign * num = 1 + 1 * 2 = 3
Solution
Python
1 2py 3class Solution: 4 def calculate(self, s): 5 ans = 0 6 num = 0 7 sign = 1 8 stack = [1] # Stack is initially 1 9 10 for c in s: 11 if c.isdigit(): 12 num = num * 10 + int(c) 13 elif c == '(': 14 stack.append(sign) 15 elif c == ')': 16 stack.pop() 17 elif c == '+' or c == '-': 18 ans += sign * num 19 sign = (1 if c == '+' else -1) * stack[-1] # Update the sign 20 num = 0 21 22 return ans + sign * num
Java
1 2java 3class Solution { 4 public int calculate(String s) { 5 int ans = 0; 6 int num = 0; 7 int sign = 1; 8 Stack<Integer> stack = new Stack<>(); 9 stack.push(sign); 10 11 for (char c : s.toCharArray()) { 12 if (Character.isDigit(c)) { 13 num = num * 10 + (c - '0'); 14 } else if (c == '(') { 15 stack.push(sign); 16 } else if (c == ')') { 17 stack.pop(); 18 } else if (c == '+' || c == '-') { 19 ans += sign * num; 20 sign = (c == '+' ? 1 : -1) * stack.peek(); 21 num = 0; 22 } 23 } 24 25 return ans + sign * num; 26 } 27}
JavaScript
1 2js 3class Solution { 4 calculate(s) { 5 let ans = 0, num = 0, sign = 1, stack = [1]; 6 7 for (let c of s) { 8 if (/\d/.test(c)) { 9 num = num * 10 + Number(c); 10 } else if (c === '(') { 11 stack.push(sign); 12 } else if (c === ')') { 13 stack.pop(); 14 } else if (c === '+' || c === '-') { 15 ans += sign * num; 16 sign = (c === '+' ? 1 : -1) * stack[stack.length - 1]; 17 num = 0; 18 } 19 } 20 21 return ans + sign * num; 22 } 23}
C++
1 2cpp 3class Solution { 4public: 5 int calculate(string s) { 6 int ans = 0, num = 0, sign = 1; 7 stack<int> stack; 8 stack.push(sign); 9 10 for (char c : s) { 11 if (isdigit(c)) { 12 num = num * 10 + (c - '0'); 13 } else if (c == '(') { 14 stack.push(sign); 15 } else if (c == ')') { 16 stack.pop(); 17 } else if (c == '+' || c == '-') { 18 ans += sign * num; 19 sign = (c == '+' ? 1 : -1) * stack.top(); 20 num = 0; 21 } 22 } 23 24 return ans + sign * num; 25 } 26};
C#
1 2csharp 3public class Solution { 4 public int Calculate(string s) { 5 int ans = 0, num = 0, sign = 1; 6 Stack<int> stack = new Stack<int>(); 7 stack.Push(sign); 8 9 foreach (char c in s) { 10 if (Char.IsDigit(c)) { 11 num = num * 10 + (c - '0'); 12 } else if (c == '(') { 13 stack.Push(sign); 14 } else if (c == ')') { 15 stack.Pop(); 16 } else if (c == '+' || c == '-') { 17 ans += sign * num; 18 sign = (c == '+' ? 1 : -1) * stack.Peek(); 19 num = 0; 20 } 21 } 22 23 return ans + sign * num; 24 } 25}
Conclusion
The above explained and provided solution in Python, JavaScript, Java, C++ and C# will correctly calculate the value of an input expression in accordance with the standard order of operations. This solution is unique in addressing the embedded parentheses, taking them into account when performing computations. The use of the stack data structure is key here, as it enables us to handle the nested operations in an efficient and structured way. In addition, converting the input string into individual characters and processing them sequentially allows the program to handle different sized numbers and complex expressions seamlessly.
The solution overall has a time complexity of O(n), where n is the length of the string. This is because each character in the string is processed exactly once, resulting in linear time complexity.
In conclusion, this calculator program brilliantly highlights the proper usage and capabilities of data structures and control flow in tackling complex operations. It's a great example of how to solve problems using the fundamental concepts of computer science and programming.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.