Hackbright Code Challenges

Calculator: Solution

Calculator: Solution

Problem

Calculator

Whiteboard

Harder

Challenge

Medium

Concepts

Stacks

Download

calculator-solution.zip


Consider an expression like:

- 9 * 2 3

We want to multiple the 2 and 3, then subtract that from 9.

We’ll scan the string, keeping separate stacks of operators and numbers. Then, as a special case, we’ll pop the last number off, so we have a number to start with. Then, we’ll pop off number and operators, performing the expression backwards.

For our example:

  • Make an operators stack of [-, *].

  • Make a numbers stack of [9, 2, 3].

  • Pop the last number, 3, off.

  • Our loop:

    • Pop off the last number, 2, and the last operator, *.

    • Multiply 2 * 3 = 6

    • Pop off the last number, 9, and the last operator, -.

    • Subtract 9 - 6 = 3

  • Return 3

def calc(s):
    """Evaluate expression."""

    # START SOLUTION

    # Convert to list of tokens
    #
    # For example: "+ 1 2" -> ["+", "1", "2"]
    tokens = s.split()

    # Start with right-most number (in a well-formed polish notation
    # expression, it must ALWAYS end with a number)
    operand2 = int(tokens.pop())

    while tokens:
        # Grab the right-most number
        operand1 = int(tokens.pop())

        # Grab the right-most operand
        operator = tokens.pop()

        # Do the math and use the result as our "right-hand" value
        # for the next time we do math

        if operator == "+":
            operand2 = operand1 + operand2

        elif operator == "-":
            operand2 = operand1 - operand2

        elif operator == "*":
            operand2 = operand1 * operand2

        elif operator == "/":
            operand2 = operand1 // operand2

    # The final result is the result of the most recent operation

    return operand2