# Postfix Expression Evaluation

Given a postfix expression, the task is to evaluate the expression and print the final value. Operators will only include the basic arithmetic operators like *, / , +, and -.

**Infix expression**: The expression of the form **a op b**. When an operator is in-between every pair of operands.

**Postfix expression**: The expression of the form **a b op**. When an operator is followed for every pair of operands.

**Input:**

The first line of input contains an integer **T** denoting the number of test cases. The next **T** lines contain a postfix expression. The expression contains all characters and **^, *, /, +, -**.

**Output:**

For each test case, in a new line, evaluate the postfix expression and print the value.

**Examples:**

Input:
T = 1
5641*+8-
Output:
2
Input:
T = 1
123+*8+
Output:
13

Stack Based ApproachWe will perform the following operation.

Iterate from left to right, if we encounter operand then push it into the stack otherwise if we encounter operator then we will do the following,

) and the second top element is the first value of the integer(n2) as stack follow last in first out manner.n1etc.+, -, *, /Pseudo Code:O(n)O(n)C++ Implementation:Output