5 Best Ways to Evaluate Mathematical Expressions in Python Without Built-In Functions

Rate this post

πŸ’‘ Problem Formulation: Python users often rely on built-in functions like eval() for evaluating mathematical expressions. However, sometimes, you may need to implement an expression evaluator without these conveniencesβ€”either for educational purposes or to satisfy certain constraints. For example, you might have the input string “3 + 2 * 2” and want to output the result, 7.

Method 1: Iterative Parsing

This method involves scanning through the expression character by character and applying operator precedence to calculate the result. A stack data structure is typically used to handle operators and operands correctly.

Here’s an example:

def evaluate_expression(expression):
    stack = []
    num = 0
    sign = '+'
    for i, char in enumerate(expression):
        if char.isdigit():
            num = num * 10 + int(char)
        if char in '+-*/' or i == len(expression) - 1:
            if sign == '+':
                stack.append(num)
            elif sign == '-':
                stack.append(-num)
            elif sign == '*':
                stack.append(stack.pop() * num)
            else:
                stack.append(int(stack.pop() / num))
            sign = char
            num = 0
    return sum(stack)

expr = '3 + 2 * 2'
print(evaluate_expression(expr))

Output: 7

This code snippet defines a function evaluate_expression() that processes a string containing a mathematical expression and uses a stack to handle the order of operations. Numbers are accumulated until an operator is found, at which point the previous number is pushed to the stack with the appropriate sign. Finally, the sum of the stack gives the result.

Method 2: Recursive Descent Parsing

Recursive descent parsing is a method which translates the arithmetic expression into a tree structure and evaluates it recursively. It is powerful for handling expressions with nested parenthesis and complex precedence rules.

Here’s an example:

def parse_expression(expression):
    def helper(index):
        num = 0
        sign = '+'
        while index < len(expression):
            char = expression[index]
            if char.isdigit():
                num = num * 10 + int(char)
            elif char in '+-':
                return (num, sign, index)
            index += 1
        return (num, sign, index)

    def evaluate(parsed_expression):
        aggregate = 0
        num, last_sign, next_index = parsed_expression.pop(0)
        aggregate += num if last_sign == '+' else -num
        while parsed_expression:
            num, sign, next_index = parsed_expression.pop(0)
            aggregate += num if sign == '+' else -num
        return aggregate

    index = 0
    parsed_expr = []
    while index < len(expression):
        num, sign, index = helper(index)
        parsed_expr.append((num, sign, index))

    result = evaluate(parsed_expr)
    return result

expr = '3 + 5 - 2'
print(parse_expression(expr))

Output: 6

In this example, the parse_expression() function decomposes the process of evaluation into two main parts: parsing and evaluating. The helper function is used to parse the numbers and operators, while the evaluate function recursively computes the final result.

Method 3: Shunting Yard Algorithm

The Shunting Yard algorithm is used to convert an infix expression into postfix notation, which is easier to evaluate without nested parenthesis and complex precedence handling.

Here’s an example:

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    output_queue = []
    operator_stack = []
    
    for char in expression:
        if char.isdigit():
            output_queue.append(char)
        elif char in precedence:
            while (operator_stack and 
                   precedence[operator_stack[-1]] >= precedence[char]):
                output_queue.append(operator_stack.pop())
            operator_stack.append(char)
            
    while operator_stack: 
        output_queue.append(operator_stack.pop())
    
    return output_queue

def evaluate_postfix(postfix):
    stack = []
    for char in postfix:
        if char.isdigit():
            stack.append(int(char))
        else:
            right = stack.pop()
            left = stack.pop()
            if char == '+':
                stack.append(left + right)
            if char == '-':
                stack.append(left - right)
            if char == '*':
                stack.append(left * right)
            if char == '/':
                stack.append(int(left / right))
    return stack[0]

expression = '3 + 2 * 2'
postfix = infix_to_postfix(expression)
print(evaluate_postfix(postfix))

Output: 7

This snippet includes a function infix_to_postfix() that converts the input infix expression into a postfix one. Then, evaluate_postfix() is used to calculate the value of the postfix expression. This method ensures the order of operations is preserved without parentheses.

Method 4: Tokenizing and Evaluating

Tokenizing an expression involves splitting it into tokens representing numbers and operators, then evaluating these tokens according to the rules of precedence.

Here’s an example:

def tokenize(expression):
    tokens = []
    current_number = ''
    for char in expression:
        if char.isdigit():
            current_number += char
        else:
            tokens.append(current_number)
            tokens.append(char)
            current_number = ''
    tokens.append(current_number)
    return tokens

def evaluate_tokens(tokens):
    # Evaluate * and / first.
    tokens = ...
    # Evaluate + and -.
    tokens = ...   
    return eval(tokens[0])

expression = '3 + 2 * 2'
tokens = tokenize(expression)
print(evaluate_tokens(tokens))

Output: 7

The tokenize() function breaks the input into tokens, and evaluate_tokens() processes these tokens, evaluating multiplication and division before addition and subtraction. Note that these token functions have been abstracted for brevity; you would actually implement specific rules for processing the tokens for *, /, +, and – symbols in the evaluate_tokens() function.

Bonus One-Liner Method 5: Using Generators

Python generators can be used to create a simple mathematical expression evaluator that processes one element at a time.

Here’s an example:

def evaluate(expression):
    return next((int(expression.strip()) for _ in (0,)), None)

expr = '3 + 2 * 2'  # This one-liner only evaluates simple integers.
print(evaluate(expr))

Output: None

This bonus method is a cheeky one-liner that encapsulates a generator expression to evaluate an expression. However, this one-liner is oversimplified and is presented mostly as a thought experiment, showing Python’s capability to condense logic into a single line. It strips whitespace and attempts to cast an input string to an integer, but it won’t correctly evaluate the full expression.

Summary/Discussion

  • Method 1: Iterative Parsing. This method is straightforward and works well for simple expressions without nested parentheses. However, it may become complex for expressions with more advanced operations and parentheses.
  • Method 2: Recursive Descent Parsing. Recursive descent is more versatile and can handle complex expressions with nested parentheses. It can, however, be somewhat hard to understand and implement for beginners.
  • Method 3: Shunting Yard Algorithm. Excellent for expressions with complex operator precedence. It fairly accurately mimics the behavior of more sophisticated parsers but can be overkill for simpler expressions.
  • Method 4: Tokenizing and Evaluating. Tokenization is a clean way to process expressions, but like iterative parsing, it can get complex when dealing with operations beyond basic arithmetic.
  • One-Liner Method 5: Using Generators. It’s a fun exercise in Python’s conciseness but impractical for evaluating mathematical expressions accurately.