Connection Status:
Competition Arena > Calculate

Calculate

TCO '03 Round 2 · 2003-10-07 · by lars2520

TCO '03 Round 2 · 2003-10-07 · by lars2520 · String Parsing
Class Name: Calculate
Return Type: int
Method Name: calc
Arg Types: (string, vector<string>)
Problem Statement

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

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
0)
"x*y+3*x"
{"x 1", "y 11"}
Returns: 14

The example from the problem statement.

1)
"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
2)
"t^003^t"
{"t 00000000000002","a 999999999"}
Returns: 64

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

3)
"(8*(Aa^(aA-1230))-aA^2+((00)))*(0-1)"
{"aA 01234","Aa 98"}
Returns: -736371772
4)
"0-2+t^30+t^30+1"
{"t 2"}
Returns: 2147483647

The largest possible result.

5)
"1+(0-t)^31-1"
{"t 2"}
Returns: -2147483648

The smallest possible result.

6)
"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.

Submissions are judged against all 32 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Calculate with a public method int calc(string expression, vector<string> variables) · 32 test cases · 2 s / 256 MB per case

Submitting as anonymous