Expression Evaluation

December 23, 2023

Problem #

Given a mathematical expression represented as a string (e.g., “(2 + 3) * 4 / 2”), design an algorithm to evaluate the expression and return the result.

Solution #

import operator

def evaluate_expression(expression):
    def apply_operator(ops, values):
        # Apply the operator to the top two values in the values stack
        operator = ops.pop()
        right = values.pop()
        left = values.pop()
        values.append(operations[operator](left, right))

    operations = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv}
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    values = []
    ops = []
    i = 0

    while i < len(expression):
        if expression[i] == ' ':
            i += 1
            continue

        if expression[i] in '0123456789':
            val = 0
            while i < len(expression) and expression[i].isdigit():
                val = (val * 10) + int(expression[i])
                i += 1
            values.append(val)
            i -= 1
        elif expression[i] == '(':
            ops.append(expression[i])
        elif expression[i] == ')':
            while ops and ops[-1] != '(':
                apply_operator(ops, values)
            ops.pop()  # Pop '('
        else:
            while ops and ops[-1] in precedence and precedence[ops[-1]] >= precedence[expression[i]]:
                apply_operator(ops, values)
            ops.append(expression[i])
        i += 1

    while ops:
        apply_operator(ops, values)

    return values[0]

# Example usage
expression = "(2 + 3) * 4 / 2"
result = evaluate_expression(expression)
result

This code fixes the precedence issue and more robustly handles numbers, operators, and parentheses. It also uses the operator module for mathematical operations, which simplifies the apply_operator function.

Solution analysis #

It uses a stack-based approach for handling operators and operands, correctly respecting mathematical precedence and parentheses. Let’s break down the key parts of the code:

Import Statement #

• import operator: This imports Python’s built-in operator module, which provides functions like add, sub, mul, and truediv for basic arithmetic operations.

The evaluate_expression Function #

• Input: A string representing a mathematical expression (e.g., “(2 + 3) * 4 / 2”).
• Output: The result of evaluating the expression.

Helper Functions and Variables #

• apply_operator: This function takes the top operator from the ops stack and applies it to the top two values in the values stack. It uses the operations dictionary to map string operators to their corresponding arithmetic functions.
• operations: A dictionary mapping string representations of operators (+, -, *, /) to their corresponding functions in the operator module.
• precedence: A dictionary defining the precedence of operators, with multiplication and division having higher precedence than addition and subtraction.

Main Algorithm #

1. Initialization: Two stacks are initialized:

   • values: For storing numerical values.
   • ops: For storing operators, including parentheses.

2. Iterating Over the Expression:

   • The expression is iterated character by character.
   • If a character is a digit, it’s part of a number. The code forms the complete number by considering subsequent digits.
   • Spaces are skipped.
   • If a character is an opening parenthesis (, it’s pushed onto the ops stack.
   • If a character is a closing parenthesis ), the code repeatedly applies the operators from the ops stack to the top values in the values stack until it encounters an opening parenthesis.
   • If a character is an operator (+, -, *, /), the code checks the precedence of the top operator in the ops stack. If the current operator has lower or equal precedence, the code applies the top operator to ensure correct order of operations.

3. Applying Remaining Operators:

   • After iterating through the expression, any remaining operators in the ops stack are applied to the values in the values stack.

4. Returning the Result:

   • The final result of the expression is at the top of the values stack and is returned.

Example Usage #

• The example demonstrates the evaluation of the expression “(2 + 3) * 4 / 2”, which correctly computes the result according to mathematical rules.

This algorithm efficiently handles different aspects of the expression, including numerical values, operator precedence, and parentheses, providing an accurate evaluation of the given mathematical expression.