Problem Statement
- Always evaluate expressions in parentheses first.
- Exponentiation next.
- Multiplication and division next.
- Addition and subtraction last.
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
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 "
", where is a sequence of 1 or more letters ('a'-'z' and 'A'-'Z'), and is an integer between -2^32 and 2^32-1, inclusive (possibly with leading zeros). - No two elements of variables will have the same
. - 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.
"0"
{"a 000000000000000000000000000000000000000999999999"}
Returns: 0
Note that since a is never used it doesn't matter that its value is bigger than 2^31-1.
"(8*(g^(a-1230))-a^2+((0)))*(0-1)"
{"a 1234","g 98"}
Returns: -736371772
"((5-x+1^x))"
{"x -100"}
Returns: 106
"5-x"
{"x -100"}
Returns: 105
"0-2^30-2^30+2^30+2^30-1+2^30+2^30"
{}
Returns: 2147483647
"A-A"
{"A 0"}
Returns: 0
"NqNGVq^(q+re+626414-816349)"
{"re 216945","NqNGVq -1","q -723028","A -342998"}
Returns: 1
"NqNGVq^(q+re+626414-816348)"
{"re 216945","NqNGVq -1","q -723028","A -342998"}
Returns: -1
"a^a"
{"a -1","b 1"}
Returns: -1
"a^b"
{"a -1","b 1"}
Returns: -1
"a^b"
{"a -1","b 2"}
Returns: 1
"a^b"
{"a -1","b -2"}
Returns: 1
"((5))"
{}
Returns: 5
"0^x"
{"x 100"}
Returns: 0
"a^b"
{"a -1","b 1"}
Returns: -1
"a^b"
{"a -2","b 0"}
Returns: 1
"a^b"
{"a 1","b -1"}
Returns: 1
"a^b"
{"a 1","b 0"}
Returns: 1
"0-(0-(0-b))-a"
{"a -1","b 1"}
Returns: 0
"0^2147000000"
{}
Returns: 0
"0-(0-b)-a"
{"a -1","b 1"}
Returns: 2
"((((((((((((((((((((((((a))))))))))))))))))))))))"
{"a -432"}
Returns: -432
"1^(2^30)-1^(2^30)"
{ }
Returns: 0
"((1+2)*(3+4)^2)^(2-1)"
{ }
Returns: 147
"a^b"
{ "a -1", "b -1" }
Returns: -1
"17*1^2147483646"
{ }
Returns: 17