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 postfix notation. To avoid ambiguity with multi-digit numbers and negative integers, all operators and operands are separated by a single space (e.g., 1 2 +, 5 3 + 2 - 6 /).
Because postfix 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 the result of a sub-expression or any integer. In the case where the operand is a negative integer, it is denoted with a minus sign in front of the integer (e.g., -3 2 + is -1). A standalone - token represents the subtraction operator, while a token such as -3 represents a negative integer. For positive integers, their plus sign will always be omitted (e.g., +3 5 + will not occur).
In postfix notation, an operator is applied to the two values immediately preceding it. The first value is the left operand and the second value is the right operand. For example, 5 2 - evaluates to 5 - 2 = 3, and
6 2 / evaluates to 6 / 2 = 3.
It is possible the expression is invalid, such as when there are not enough operands for an operator or when extra operands remain after evaluation (e.g., 1 + or 1 2 3 +), in which case your program should output bad expression. You can otherwise assume the expressions 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.