Calculator Language
Time limit1sMemory limit128 MB
Evaluate expressions in a tiny language with right-associative equal-precedence operators, assignment, and right-to-left operand evaluation, then report changed variables.
- Level
Medium7 of 10
- Topics
- Implementation, Recursion, String, Simulation
- Solved
- No attempts yet
Problem
Calculator Language (CL) supports assignment, positive and negative integers, and simple arithmetic. The characters allowed in a CL statement are:
All operators have the same precedence and are right associative, so 15 - 8 - 3 = 15 - (8 - 3) = 10. As expected, brackets force the expression inside them to be evaluated first, and brackets may be nested to any depth. An expression never has two operators next to each other (even if separated by a bracket); an assignment operator is always immediately preceded by a variable; and the leftmost operator on a line is always an assignment. For readability, spaces may be inserted freely, except between a negative sign and its number. A negative sign appears only immediately before an integer. All variables start at 0 and keep their values until they are changed explicitly.
In addition, the second operand is always evaluated first. For example, (A = 10) / (A = 5) first evaluates (A = 5), then evaluates (A = 10), and finally computes 10 / 5. Every integer division follows the C/C++ integer-division rule (truncation toward zero), and there is never a division by zero.
Write a program that reads and evaluates expressions written in this language. Each expression occupies one line and contains at least one assignment operator, possibly more.
Input
The input is a series of lines, each containing one valid CL expression. No line is longer than 100 characters. The input ends with a line containing a single #.
Output
Print one line of output for each input line. Each output line lists the final values of every variable whose value changes as a result of evaluating that expression. If more than one variable changes, list them in alphabetical order, separated by , (a comma and a space). If a variable changes more than once within an expression, print only its final value. A variable is considered changed if its value after the expression is evaluated differs from its value before. If no variable changes value, print No Change. Follow the format shown in the examples exactly.