Calculate | Topcoder Archive

Problem Statement

You must write a class Calculate, with a method calc, which takes a String expression, where expression is a mathematical expression. You should calculate the value of the expression, using the standard order of operations:

Always evaluate expressions in parentheses first.
Exponentiation next.
Multiplication and division next.
Addition and subtraction last.

Operators with the same precedence should be evaluated from left to right. So 2^3^2 = (2^3)^2 = 64, and 3-2+1 = (3-2)+1 = 2

Thus, if expression = "1+2*3^(1+1)-2", we first calculate (1+1), and get "1+2*3^2-2". Next we apply exponentiation and get "1+2*9-2". Then multiplication and division gives us "1+18-2". Last, addition and subtraction, left to right, gives 17.

Furthermore, you will be given a String[] variables each of whose elements represents a variable which may be used in expression. Each element of variables will be formatted as "<variable> <value>", where <variable> is a sequence of 1 or more letters ('a'-'z' and 'A'-'Z'), and <value> is an integer. For example, if variables = {"x 1", "y 11"}, and expression = "x*y+3*x", we substitute the values for the variables to get 1*11+3*1 = 14.

The expression will conform to the following grammar:

<expression> ::= (<expression>) | <expression><op><expression> | <val>
<op>::= '+'|'-'|'/'|'*'|'^'
<val>::= a sequence of 1 or more digits or a <variable> from variables

Definition

Class:: Calculate
Method:: calc
Parameters:: String, String[]
Returns:: int
Method signature:: int calc(String expression, String[] variables)
(be sure your method is public)

Notes

All of the intermediate and final results of both division and exponentiation will be integers between -2^31 and 2^31 - 1, inclusive. (see constraints)
Variable names are case sensitive.

Constraints

expression will include only the characters '0' to '9', '+', '-', '*', '/', '^', '(', and ')' and letters ('a'-'z' and 'A'-'Z').
expression will be well-formed, conforming to the grammar in the problem statement.
The final result, and all intermediate results will be integers in the range -2^31 to 2^31-1, inclusive. This includes all numbers and variables, so "0*10000000000" is not allowed, nor is "0*a", {"a 10000000000"}.
expression will not result in division by 0 or 0^x, for x less than or equal to 0.
variables will have between 0 and 50 elements, inclusive.
Each element of variables will be formatted as "<variable> <value>", where <variable> is a sequence of 1 or more letters ('a'-'z' and 'A'-'Z'), and <value> is an integer between -2^32 and 2^32-1, inclusive (possibly with leading zeros).
No two elements of variables will have the same <variable>.
Each variable in expression will be found in variables.
expression will contain between 1 and 50 characters, inclusive.
Each element of variables will contain between 3 and 50 characters, inclusive.

Examples

```
"x*y+3*x"
```
```
{"x 1", "y 11"}
```
```
Returns: 14
```
The example from the problem statement.

"x^p*2^(2^p)/t^p^t+xx*n^v"

{"x 53", "xx 32", "p 3","t 2","n -1","v -21"}

Returns: 595476

"t^003^t"

{"t 00000000000002","a 999999999"}

Returns: 64

Substituting, we get 2^3^2 = 8^2 = 64.

"(8*(Aa^(aA-1230))-aA^2+((00)))*(0-1)"

{"aA 01234","Aa 98"}

Returns: -736371772

"0-2+t^30+t^30+1"

{"t 2"}

Returns: 2147483647

The largest possible result.

"1+(0-t)^31-1"

{"t 2"}

Returns: -2147483648

The smallest possible result.

```
"((5-x+1^x))"
```
```
{"x -100"}
```
```
Returns: 106
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.