Equation

Interview

Time limit1sMemory limit128 MB

Summary

Evaluate a postfix expression containing at most one occurrence of variable X as a linear function a*x+b, then solve a*x+b=0 for x as a reduced fraction, handling no-solution and infinite-solution cases.

Level: Medium5 of 10
Topics: Stack, Math, Implementation
Solved: No attempts yet

Problem

Write a program that solves the equation f(x) = 0, where f(x) is given in postfix notation.

f(x) is a postfix expression made up of digits, the operators +, -, *, /, and the variable x. The variable x appears at most once in the whole expression.

For example, the left-hand side f(x) of the equation (4x + 2) / 2 = 0 is written in postfix notation as:

4 X * 2 + 2 /

The solution of f(x) = 0 is then x = -1/2.

Input

The first line contains the equation f(x) in postfix notation. The variable x is written as the uppercase letter X, and the expression consists of the operators +, -, *, / and the single digits 0-9. X appears at most once. Tokens are separated by spaces, and there are at most 30 of them.

Only inputs whose solution can be found without dividing by zero are given.

Output

If f(x) = 0 has exactly one solution, print it as X = p/q, where p and q are coprime and q is positive. If the solution is 0, print X = 0/1.

If there is no solution, print NONE.

If there is more than one solution, print MULTIPLE.

Examples4

Example 1
Input
```
4 X * 2 + 2 /
```
Expected output
```
X = -1/2
```
Example 2
Input
```
1 2 / 2 4 / - X *
```
Expected output
```
MULTIPLE
```
Example 3
Input
```
1 1 X 2 + / /
```
Expected output
```
NONE
```
Example 4
Input
```
3 X * 7 -
```
Expected output
```
X = 7/3
```