Basic Calculator LeetCode

Key takeaways:
Calculates complex expressions by parsing digits, operators, and parentheses.
Uses stack-based handling to manage sign context in nested expressions.
Efficiently evaluates expressions with $O(n)$ time and space complexity.

Imagine you’re developing a calculator application that allows users to input complex arithmetic expressions for evaluation. A user, Sarah, inputs the expression $2 + (3 - 1) + 5 - 6$ into the calculator. Your program must accurately evaluate this expression to provide Sarah with the correct result.

Ensuring accurate evaluation of arithmetic expressions is crucial for calculator applications like yours. Users rely on these tools for precise calculations in various fields, including education, finance, and engineering. By correctly interpreting parentheses, handling multi-digit integers, and respecting operator precedence, your calculator can provide Sarah with reliable results, enhancing her trust in your application.

Problem statement

Given a string s, representing a valid arithmetic expression, your task is to implement a basic calculator to evaluate the expression and return the result. The expression will contain non-negative integers, plus (+), minus (-), parenthesis, and spaces.

The program should be able to handle multi-digit integers, properly interpret parentheses to determine the order of operations, and account for positive and negative signs within the expressions.

Example

Algorithm

To efficiently evaluate arithmetic expressions provided as strings, we adopt a stack-based approach combined with iterative parsing of the input expression. The main idea is to traverse the expression character by character, appropriately handling digits, operators, and parentheses to compute the final result.

Initialization: We initialize several variables, including cur to track the current operand being processed, res to store the running total of the expression, sign to represent the current sign and stack to maintain the sign context within parentheses.
Iterative parsing: We iterate through each character of the input expression. Depending on the type of character encountered (digit, operator, or parenthesis), we perform specific operations, such as updating the current operand cur, adjusting the current sign sign, or manipulating the stack to handle parentheses.
Operand and operator handling: When encountering digits, we appropriately combine them to form multi-digit operands. For operators (+, -), we update the result res based on the current operand cur and sign sign, and reset cur to 0 to prepare for the next operand.
Parentheses handling: We utilize a stack to keep track of the sign context within parentheses. When an opening parenthesis is encountered, we push the current sign onto the stack. Upon encountering a closing parenthesis, we pop the top sign from the stack to restore the sign context.
Final result calculation: After parsing the entire expression, we add the final operand cur multiplied by the final sign sign to the running total res, yielding the ultimate result of the arithmetic expression.

def calculate(s):
  # Define and initialize parameters
  cur = 0
  res = 0
  sign = 1
  stack = [sign]  
  # Iterate through the string 
  for c in s:
      # If current character is a digit
      if c.isdigit():
          cur = cur * 10 + int(c)
      # If current character is an opening paranthesis   
      elif c == '(':
          stack.append(sign)
      # If current character is a closing paranthesis  
      elif c == ')':
          stack.pop()
      # If current character is an + or - sign 
      elif c == '+' or c == '-':
          res += sign * cur
          if c == '+':
              sign = 1 * stack[-1]
          elif c == '-':
              sign = -1 * stack[-1]
          cur = 0
  return res + sign * cur
# Test cases
exp1 = "1 + 1"
exp2 = " 2-1 + 2 "
exp3 = "(1+(4+5+2)-3)+(6+8)"
print("The answer for the expression", exp1, "is:", calculate(exp1)) # 2
print("The answer for the expression", exp2, "is:", calculate(exp2)) # 3
print("The answer for the expression", exp3, "is:", calculate(exp3)) # 23

Basic calculator in Python

Explanation

In the above code in Python:

Line 1: We initialize the calculate function, which takes a string s as input.
Line 3: cur is initialized to 0 to track the current number being formed.
Line 4: res is initialized to 0, used to store the running result.
Line 5: sign is set to 1, representing the current number’s sign (positive or negative).
Line 6: stack is initialized with sign, used to handle signs within parentheses.
Line 8: We start iterating through each character c in the string s.
Line 10: Checks if c is a digit.
Line 11: If it is, updates cur by multiplying its current value by 10 (to shift left) and adding the integer value of c.
Line 13: Checks if c is an opening parenthesis '('.
Line 14: If it is, pushes sign onto stack to save the current context.
Line 16: Checks if c is a closing parenthesis ')'.
Line 17: If it is, pops the top value from stack to restore the previous sign context.
Line 19: Checks if c is either '+' or '-'.
Line 20: If it is, adds cur * sign to res (updating the result with the last number and its sign).
Lines 21–22: If c is '+', sets sign to 1 * stack[-1] to keep the sign positive.
Lines 23–24: If c is '-', sets sign to -1 * stack[-1] to set the sign as negative.
Line 25: This resets cur to 0 to start capturing the next number.
Line 26: After the loop, adds the final cur * sign to res, ensuring the last number is included in the result and returns res as the calculated result of the expression.

Time complexity

The time complexity of the provided code is $O(n)$ , where $n$ is the length of the input string s. This is because the code iterates through each character of the input string exactly once to evaluate the arithmetic expression.

Space complexity

The space complexity is $O(n)$ , as the space required grows linearly with the size of the input string s. The space usage primarily comes from the stack data structure, which can grow up to the size of the input string in the worst-case scenario where every character is an opening parenthesis.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources