Leetcode solution 224: Basic Calculator

Problem Statement 

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

A generic way for solving those calculating numbers problems is to use stack. More specifically, use two stacks: one stack for the operator and the other for the operands.

A few caveats

• Pay attention to the order when popping out operands and calculate, the order matters. 
• The parenthesis matters, 2 - 1 + 2 = 3, while 2 - (1+2) = -1 = 2 - 1 - 2 if you want to remove the bracket you need to change the sign 
• "1000" is a valid expression without any operators 
• The number might not be just single digit, so need to read the char and convert the numbers

Solutions

Standard generic way

Keep two stacks, operator and operands. When we see left bracket, keep pushing to the stack. We calculate the values as normal within the inner most bracket. When we see right bracket, calculate and pop out the left bracket

Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

Use the sign method with one stack

The thought process is very similar to use the stacks, in this method, the clever part is it uses only one stack and also pushed a sign. +1 for "+" and -1 for "-1". Whenever there is a left bracket, you push the existing result and the sign into the stack. Whenever there is a right bracket, you pop up the sign and the value. Pretty neat!

Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

References

• Leetcode discussion on the clean solution