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 stackbased 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 builtinoperator
module, which provides functions likeadd
,sub
,mul
, andtruediv
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 theops
stack and applies it to the top two values in thevalues
stack. It uses theoperations
dictionary to map string operators to their corresponding arithmetic functions.operations
: A dictionary mapping string representations of operators (+
,
,*
,/
) to their corresponding functions in theoperator
module.precedence
: A dictionary defining the precedence of operators, with multiplication and division having higher precedence than addition and subtraction.
Main Algorithm #

Initialization: Two stacks are initialized:
values
: For storing numerical values.ops
: For storing operators, including parentheses.

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 theops
stack.  If a character is a closing parenthesis
)
, the code repeatedly applies the operators from theops
stack to the top values in thevalues
stack until it encounters an opening parenthesis.  If a character is an operator (
+
,
,*
,/
), the code checks the precedence of the top operator in theops
stack. If the current operator has lower or equal precedence, the code applies the top operator to ensure correct order of operations.

Applying Remaining Operators:
 After iterating through the expression, any remaining operators in the
ops
stack are applied to the values in thevalues
stack.
 After iterating through the expression, any remaining operators in the

Returning the Result:
 The final result of the expression is at the top of the
values
stack and is returned.
 The final result of the expression is at the top of the
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.