Connection Status:
Competition Arena > BadParser

BadParser

TCO04 Round 1 · 2004-09-07 · by AdminBrett

TCO04 Round 1 · 2004-09-07 · by AdminBrett · Simple Math, String Parsing
Class Name: BadParser
Return Type: int
Method Name: evaluate
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You and a partner have teamed up for a coding project. He is writing the front-end of an arithmetic expression parser, and you are writing the back-end. The expressions are pretty simple, with normal arithmetic operations and no parentheses. As usual, he stayed up too late and made a terrible oversight. His parser spits out an expression tree where the precedence and associativity of the operators may be ignored. For example, let's say his program is given the expression "5+2-3-4*2". Each operator is supposed to be left associative, but his program could spit out the wrong tree: 
       His tree                    Correct Tree
          +                             -
        /   \                        /     \
       5     -                     -         *
           /   \                 /   \     /   \
          2     -               +     3   4     2
              /   \           /   \
             3     *         5     2
                 /   \
                4     2
The expressions should be interpreted as follows:
  • 1) As usual, the order of operations gives * and / highest precedence whereas + and - have lowest. * and / have equal precedence. In addition, + and - have equal precedence.
  • 2) Amongst operations of equal precedence, process the leftmost operation first.
Adhering to these rules, the input above would be processed to produce the Correct Tree. In such a tree, lower nodes are processed before higher nodes. The value of a number node is the number itself. The value of an operation node is that operation applied to the values of its left and right subnodes (the value of the left subnode belongs on the left side of the operation). The value of the tree is the value of the top node (called the root node). Unfortunately, your partner's front-end may have violated rules 1 and 2 numerous times. Luckily the ordering of his tree is not messed up. This means that an inorder traversal of the tree beginning with the root will produce the original expression. Inorder traversal pseudocode follows:
InorderTraverse(node) {
	if (left subtree of node exists) 
		InorderTraverse(root of left subtree)
	Print the contents of node
	if (right subtree of node exists) 
		InorderTraverse(root of right subtree)
}
Your program will take a String[] badTree describing his tree, and will return an int which is the correct value of the expression he parsed. All operations are integer operations so division truncates results. For example 5/3=1, and -5/3 = -1.

Each element of badTree will be in one of two forms (quotes for clarity):
  • 1) "op X Y" : op is one of *,/,+,-. X,Y are integers referencing other elements of badTree (0-indexed). X refers to the node's left child and Y refers to the node's right child.
  • 2) "N" : N is a non-negative integer with no extra leading zeros.

Constraints

  • badTree will contain between 1 and 50 elements inclusive.
  • Each element of badTree will be in one of the following forms (quotes for clarity):1) "op X Y" where X and Y are integers, with no extra leading zeros, between 0 and M-1 inclusive. op must be *,+,-, or /. Here M denotes the number of elements in badTree.2) "N" where N is a nonnegative integer with no extra leading zeros between 0 and 1000 inclusive.
  • The elements of badTree will describe a single tree, with element 0 acting as root.
  • The return value, and the value of any subtree of the correct tree will all be between -100000 and 100000 inclusive.
  • The computation of the return value, and the value of any subtree of the correct tree will not require division by 0.
Examples
0)
{"+ 1 2","5","- 3 4","2","- 5 6","3","* 7 8","4","2"}
Returns: -4

The example in the problem statement.

1)
{"- 1 2","5","- 3 4","2","- 5 6","3","* 7 8","4","2"}
Returns: -8

The example in the problem statement with the + replaced by a -.

2)
{"* 1 2","5","- 3 4","2","- 5 6","3","* 7 8","4","2"}
Returns: -1

The example in the problem statement with the + replaced by a *.

3)
{"99"}
Returns: 99
4)
{"* 1 2","+ 3 4","+ 5 6","200","200","200","200"}
Returns: 40400

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

Coding Area

Language: C++17 · define a public class BadParser with a public method int evaluate(vector<string> badTree) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous