Equation Elation

Interview

Time limit1sMemory limit128 MB

Summary
Repeatedly reduce an arithmetic expression on the left of an equals sign by performing one operation at a time in precedence order, printing each intermediate line.
Level

Medium4 of 10

Topics
Simulation, Implementation, String, Math
Solved
No attempts yet

Problem

An elementary-school algebra textbook author needs a program that solves simple algebra equations one step at a time, so the solutions manual can be prepared without human error.

Every problem is an algebraic equality made of integer constants, the four basic arithmetic operators (+, -, *, /), an equals sign, and a variable, for example 12 - 4 * 3 = x.

The equation must not merely be solved; it must be reduced one operation at a time following the standard order of operations. All multiplications and divisions are performed first, from left to right, and then all additions and subtractions, from left to right. At each step exactly one operation — the left-most operation of the highest precedence currently present — is carried out, and the resulting equation is written on its own line. You may assume every division is exact (it always yields an integer).

Input

The input contains several equations, one per line, until end of file.

Each equation has from 1 to 20 operations and therefore from 2 to 21 integer operands (there is always exactly one more operand than there are operators). An operand may carry a leading unary sign (+ or -). Spaces between operators and operands are optional and may be absent entirely. The variable name on the right-hand side is 1 to 8 alphabetic characters.

Output

For each equation, first print the equation itself, then print one line after every single operation, until only one value remains on the left-hand side.

Format each line with exactly one space between every operand, operator, and the = sign (e.g. 2 * -3 + -6 - 4 = r). Write a negative operand with a leading -; write a non-negative operand with no sign (a leading unary + from the input is dropped). Separate the output of consecutive equations with one blank line.

Examples5

  1. Example 1

    Input
    3 * 4 + 4 - 1 / 1 = xyzzy
    12 + 2 * 12 / 2 - 1 = y
    2 * -3 + -6 - +4 = r
    2*-3+-6-+4=r
    
    Expected output
    3 * 4 + 4 - 1 / 1 = xyzzy
    12 + 4 - 1 / 1 = xyzzy
    12 + 4 - 1 = xyzzy
    16 - 1 = xyzzy
    15 = xyzzy
    
    12 + 2 * 12 / 2 - 1 = y
    12 + 24 / 2 - 1 = y
    12 + 12 - 1 = y
    24 - 1 = y
    23 = y
    
    2 * -3 + -6 - 4 = r
    -6 + -6 - 4 = r
    -12 - 4 = r
    -16 = r
    
    2 * -3 + -6 - 4 = r
    -6 + -6 - 4 = r
    -12 - 4 = r
    -16 = r
    
  2. Example 2

    Input
    12 - 4 * 3 = x
    
    Expected output
    12 - 4 * 3 = x
    12 - 12 = x
    0 = x
    
  3. Example 3

    Input
    5 + 3 = sum
    
    Expected output
    5 + 3 = sum
    8 = sum
    
  4. Example 4

    Input
    100 / 5 / 2 = q
    
    Expected output
    100 / 5 / 2 = q
    20 / 2 = q
    10 = q
    
  5. Example 5

    Input
    -10 + 4 * 2 = ans
    
    Expected output
    -10 + 4 * 2 = ans
    -10 + 8 = ans
    -2 = ans