(E) Reverse Polish notation¶

Goal: I will learn how to use array type of C++.

Instructions: Create a new project: student/08/reverse_polish.

Reverse Polish notation shows an expression such that the operands of each subexpression is written before the operator. For example, the expression 2 + 3 is written as 2 3 +. In the same way, the more complex expression 2 * 3 + 4 in the Polish notation is as 2 3 * 4 +, and the expression 2 + 3 * 4 as 2 3 4 * +. Polish notation has the benefit that parentheses become unnecessary. For example, the expression (2 + 3) * 4 in Polish notation is 2 3 + 4 *.

Moreover, evaluation of the expression is easy. You can use an array that can be thought as a stack such that the first element of the array is the bottom element of the stack. An expression is read from left to right. Each time an operand occurs, it is added at the top of the stack. When an operator occurs, the two topmost elements are removed from the stack, the operator is applied to the these operand, and the result of the operation is added at the top of the stack.

For example, in the case of expression 2 3 + 4 *, the steps described above look like this:

The small arrow under the expression tells the reading point.

When the whole expression is evaluated, the stack should contain exactly one element that is the result of the whole expression. If this is not the case, the expression was not valid.

Implement a program that takes an expression in Polish notation as its input, evaluates the expression, and prints the result of the evaluation. At the same time, the program checks whether the given expression was a valid expression in Polish notation.

If the given expression was valid, the return value of main function is EXIT_SUCCESS. Otherwise the main function returns EXIT_FAILURE.

Example executions of the program:

Input an expression in reverse Polish notation (end with #):
EXPR> 2 3 4 * + #
Correct: 14 is the result

The program informs if there are too few operands or operators:

Input an expression in reverse Polish notation (end with #):
EXPR> 2 3 4 * #
Error: Too few operators

Input an expression in reverse Polish notation (end with #):
EXPR> 2 3 4 * + + #
Error: Too few operands

Each expression must start with a numeric character. If this is not the case, the program prints as follows:

Input an expression in reverse Polish notation (end with #):
EXPR> + 2 3 #
Error: Expression must start with a number

The program knows the arithmetic operators: +, -, * ja /. If some other operator is given, the program prints as follows:

Input an expression in reverse Polish notation (end with #):
EXPR> 2 3 4 * % #
Error: Unknown character

The program recognizes division by zero:

Input an expression in reverse Polish notation (end with #):
EXPR> 2 0 / 3 + #
Error: Division by zero

Tips for completing the assignment:

• A (valid) input consists of digits and the aforementioned operator symbols. Therefore, it is a good idea to read the input symbols as char type. However, to perform calculations, numeric symbols must be converted to integers.
• It is sufficient that the program works with single-digit numbers. If you want your program to work also with bigger numbers, you can use the putback function of ifstream class. The function puts the latest read character back to the input stream. More precisely, you can first read a character as char type. If is was a numeric character, you can put it back to the input stream, and then read an integer from the input stream. In this way, you can read also a bigger number consisting of several digits at the same time.
• Note from the previously described evaluation algorithm that the array (stack) stores only numbers, not operator symbols.
• You can assume that the input is no longer than 80 characters.