Test Case

Data Structures Algebraic to RPN Converter/Evaluator -

Testcase

1 + 2 Solution: 3

3 - 4 Solution: -1

5 / 6 Solution: 0.83

7 * 8 Solution: 56

(2 + 3) * (4 * 5) Solution: 100

0 / 5 Solution: 0

5 / 0 Solution: Error! Division by 0

((2 + 3) / 5 + (7 + 3) / 10) / 2 Solution:

1 Additional test data from class: ((1 + 6) * 7 / 9) 16 Solution: -10.56 ((2 + 3) * 10 (7 2) / 5) Solution: 49 ((2 * 3) + 4) - ( 12 / 5) + (3 * (5 / 3)) Solution: 12.6 3 * (10 / (5 3)) * (7 + 2) Solution: 135 (12 + 5) (3 / 6) * 10 Solution: 12 6 / (5 2) + (7 4) * (10 5) Solution: 17 Note: Pseudocode provided does not include state for spaces in input.but testcase above uses them for readability. If you added additional state for space in input, make sure it does nothing but return back to state 0 and does not alter the pseudocode in any other way

Dijkstra's Shunting-Yard Algorithm: NOTE: Modified to include only numbers, operators, and parentheses. - While there are tokens to be read: - Read a token. - If the token is a number, then add it to the output queue. - If the token is an operator, o1, then: - while there is an operator token, o2, at the top of the stack, and o1 is left-associative and its precedence is less than or equal to that of o2. NOTE: Do we need to be concerned about associativity? See note below. - pop o2 off the stack, onto the output queue; - push o1 onto the stack. - If the token is a left parenthesis, then push it onto the stack. - If the token is a right parenthesis: - While the token at the top of the stack is not a left parenthesis - pop operator off the stack onto the output queue. - Pop the left parenthesis from the stack, but not onto the output queue. Note: If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. - When there are no more tokens to read: (ie end of input string) - While there are still operator tokens in the stack: - Pop the operator onto the output queue. Note: If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. Note: Associativity is only needed when the operators in an expression have the same precedence. Usually + and - have the same precedence. Consider the expression 74+2. The result could be either: (74)+2=5 when + and are left-associative or 7(4+2)=1 when + and are right-associative. Usually the addition, subtraction, multiplication, and division operators are left-associative, while the exponentiation, assignment and conditional operators are right-associative. To prevent cases where operands would be associated with two operators, or no operator at all, operators with the same precedence must have the same associativity. Dijkstra's Shunting-Yard Algorithm: NOTE: Modified to include only numbers, operators, and parentheses. - While there are tokens to be read: - Read a token. - If the token is a number, then add it to the output queue. - If the token is an operator, o1, then: - while there is an operator token, o2, at the top of the stack, and o1 is left-associative and its precedence is less than or equal to that of o2. NOTE: Do we need to be concerned about associativity? See note below. - pop o2 off the stack, onto the output queue; - push o1 onto the stack. - If the token is a left parenthesis, then push it onto the stack. - If the token is a right parenthesis: - While the token at the top of the stack is not a left parenthesis - pop operator off the stack onto the output queue. - Pop the left parenthesis from the stack, but not onto the output queue. Note: If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. - When there are no more tokens to read: (ie end of input string) - While there are still operator tokens in the stack: - Pop the operator onto the output queue. Note: If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. Note: Associativity is only needed when the operators in an expression have the same precedence. Usually + and - have the same precedence. Consider the expression 74+2. The result could be either: (74)+2=5 when + and are left-associative or 7(4+2)=1 when + and are right-associative. Usually the addition, subtraction, multiplication, and division operators are left-associative, while the exponentiation, assignment and conditional operators are right-associative. To prevent cases where operands would be associated with two operators, or no operator at all, operators with the same precedence must have the same associativity