You are to write a C/C++ program that takes in arithmetic expressions and then evaluates the expressions.
Your program needs to support four operators: + (add), - (subtract), * (multiply), and / (divide). The operators follow your common C arithmetic definition, including division gives the quotient and discards the remainder (e.g. 3 / 2 is 1). Note C allows negative divisors (e.g. 3 / -2 is a valid expression and gives -1).
The expression will be in prefix notation (also known as Polish notation). To avoid ambiguity with multi-digit numbers, all operators and operands are separated by a single space (e.g., + 1 2, / - + 5 3 2 6).
Because prefix notation inherently defines the order of operations, there are no parentheses in the expressions, and you do not need to implement specific precedence rules (like multiply/divide over add/subtract).
Note that operands can be a sub-expression or any integer. In the case where the operand is a negative integer, it is denoted with a minus sign in the front of the integer (e.g., + -3 2 is -1). For positive integers, their plus sign will always be omitted (e.g., + +3 5 will not occur).
It is possible the expression is invalid (e.g., missing operands or trailing trailing characters like + 1 or + 1 2 3), in which case your program should output bad expression. You can otherwise assume the expression characters are valid.
You can assume that the operator arguments and intermediate results are always in the range [-4*10^9, 4*10^9], and can be stored in a long type variable. You can also assume that division by 0 will never occur.
Your program MAY use C++ standard library headers.
A new line containing the number of arithmetic expressions to be evaluated (M), with the expressions starting on the next line, one expression per line.
0 < M <= 10^5
You can also assume that the sum of all expression lengths l_sum <= 2 * 10^6.
The expression evaluation outcome, one outcome per line. Each outcome should be newline ('\n') terminated.