Evaluating Mathematical Expressions with one stack in Python

(Leetcode: 224. Basic Calculator)

In this tutorial, we will learn how to evaluate mathematical expressions using stacks in Python. We will start with a simple approach and then gradually modify it to handle more complex expressions.

Examples

Example 1:

Input:

s = "1 + 1"

Output:

2

Example 2:

Input:

s = " 2-1 + 2 "

Output:

3

Example 3:

Input:

s = "(1+(4+5+2)-3)+(6+8)"

Output:

23

Basic approach

Let’s start with a basic approach to evaluate a simple expression like 4+5-2. We can iterate through the string and keep track of the previous digit, result, and sign using the prev_dig, res, and earlier_sign variables respectively. When we encounter a digit, we update prev_dig. When we encounter a + or -, we update res by adding the product of prev_dig and earlier_sign, and update earlier_sign to 1 or -1 respectively. Finally, we update res by adding the product of prev_dig and earlier_sign to handle the last digit.

s = '4+5-2'
prev_dig = 0
res = 0
earlier_sign = 1
for ch in s:
    if ch == '(':
        pass
    elif ch.isdigit():
        prev_dig = prev_dig*10 + int(ch)
    elif ch == '+':
        res = res + (prev_dig * earlier_sign)
        earlier_sign = 1
        prev_dig = 0  # Making 0 again #
    elif ch == '-':
        res = res + (prev_dig*earlier_sign)
        earlier_sign = -1
        prev_dig = 0  # Making 0 again #

res = res + (prev_dig * earlier_sign)  # Evaluate the pending expression#

print(res)

Output:

7

In the above code, we have used the isdigit() method to check if the current character is a digit. We have also used the int() method to convert the character into an integer.

Handling parentheses

Now suppose we encounter parentheses in the input expression. When we encounter an opening bracket, we know that the expression within the brackets needs to be evaluated first. So, we append the current result and sign onto the stack and reset them to their initial values.

When we encounter a closing bracket, we know that the expression within the brackets has been fully evaluated. So, we need to pop the values from the stack and re-evaluate the expression. However, there’s a catch here — since the values are stored on a stack, we need to use the last result instead of prev_dig when re-evaluating the expression.

So, instead of res = res + (prev_dig * earlier_sign) when encountering a + or -, we need to use res = stack[-1][0] + (res * earlier_sign) to evaluate the expression. Here, stack[-1][0] represents the result and stack[-1][1] represents the sign from the previous stack frame.

After evaluating the expression within the brackets, we can pop the values from the stack and update the current result and sign accordingly. This way, we can ensure that the order of operations is maintained while evaluating the expression.

    elif ch == '(':
        stack.append(res)
        stack.append(earlier_sign)

        #Neutralize everything#
        res = 0
        earlier_sign = 1

    elif ch == ')':
        # Evaluate the pending expression#
        res = res + (prev_dig * earlier_sign)

        #But still stack contains some values added by oppening brac#
        earlier_sign = stack.pop()
        prev_dig = stack.pop()
        res = prev_dig + (res * earlier_sign)  # Re-evaluate#

        prev_dig = 0 #Neutralize to avoid conflict#

So, whole code will look like this:

s = "(1+(4+5+2)-3)+(6+8)"
prev_dig = 0
res = 0
earlier_sign = 1

stack = []


for ch in s:
    if ch.isdigit():
        prev_dig = prev_dig*10 + int(ch)

    elif ch == '+':
        res = res + (prev_dig * earlier_sign)
        earlier_sign = 1
        prev_dig = 0  # Making 0 again #

    elif ch == '-':
        res = res + (prev_dig*earlier_sign)
        earlier_sign = -1
        prev_dig = 0  # Making 0 again #

    elif ch == '(':
        stack.append(res)
        stack.append(earlier_sign)

        #Neutralize everything#
        res = 0
        earlier_sign = 1

    elif ch == ')':
        # Evaluate the pending expression#
        res = res + (prev_dig * earlier_sign)

        #But still stack contains some values added by oppening brac#
        earlier_sign = stack.pop()
        prev_dig = stack.pop()
        res = prev_dig + (res * earlier_sign)  # Re-evaluate#

        prev_dig = 0  # Neutralize to avoid conflict#

res = res + (prev_dig * earlier_sign)  # Evaluate the pending expression#

print(res)