Programming Assignment 3 - Algebraic Simplification

Advanced Programming II, Fall 2001

Due Date

This assignment is due by 2:00 p.m. on Thursday, 18 October.

See the assignment turn-in page (last modified on 11 September 2001) for instructions on turning in your assignment.

The Problem

Write a program that reads from standard-in a set of algebraic equations and writes to standard-out the most simplified version of the equation sets possible.

Input consists of a sequence of sets of algebraic equations. Each equation set is separated from the next equation set by a blank line (a line containing nothing but a new line); blank lines in excess of those needed to separate equation sets should be ignored.

An algebraic equation set is a sequence of one or more lines; each line contains a single algebraic equation. An algebraic equation has the form

expression = expression

and an expression can have any of the following forms:

A single letter: a, b, c, . . ., x, y, z.
A decimal integer: d₁. . .d_n, where d is one of the decimal digits 0, 1, . . ., 8, 9. Decimal integers may be arbitrarily long.
An expression followed by an operator followed by an expression
expression operation expression, where
operation is one of the binary operators '+', '-', '*', or '/'; white space may appear on either side of the operator. precedence and associativity of the operators are the same as they are for C++.

Any equation set not following this syntax is syntactically incorrect.

Each input equation set is independent of the other equation sets.

Output

The output should be in the same form as the input: a sequence of sets of algebraic equations separated by blank lines. Equation sets should be output in the same order as input. If an input equation set a syntactically incorrect, the output should contain a brief error message describing the problem.

Output equation sets should be as simple as possible. An equation set is simple when none of the equations in the set contain possible operations. An operation is possible if both of the operation's operands are known. For example, the equation set

x = 3

is simple because it contains no operations. The equation set

y = x + 100000000000000000000000000000000000000000000000000000000000000000

is simple because none of the remaining operations are possible (x being an unknown). The equation set

x = 4 - y
y = x + 100000000000000000000000000000000000000000000000000000000000000000

is not simple because the + is a possible operator; the equation set can be further simplified to

x = -49999999999999999999999999999999999999999999999999999999999999998
y = 50000000000000000000000000000000000000000000000000000000000000002

Testing

I won't be providing any test cases for this problem; you're on your own.

This page last modified on 11 October 2001.