Operand stack: This stack will be used to keep track of numbers.

Operator stack: This stack will be used to keep operations (+, -, *, /, ^)

Order of precedence of operations–

^ (Exponential)

/ *

+ –

Note: brackets ( ) are used to override these rules.

Let’s define the Process: (will be used for main algorithm)

Pop out two values from operand stack, let’s say it is A and B.

Pop out operation from operator stack. let’s say it is ‘+’.

Do A + B and push the result to the operand stack.

Algorithm:

Iterate through given expression, one character at a time

If the character is an operand, push it to the operand stack.

If the character is an operator,

If the operator stack is empty then push it to the operator stack.

Else If the operator stack is not empty,

If the character’s precedence is greater than or equal to the precedence of the stack top of operator stack, then push the character to the operator stack.

If the character’s precedence is less than the precedence of the stack top of operator stack then do Process (as explained above) until character’s precedence is less or stack is not empty.

If the character is “(“, then push it onto operator stack.

If the character is “)”, then do Process (as explained above) until the corresponding “(” is encountered in operator stack. Now just pop out the “(“.

Once the expression iteration is completed and operator stack is not empty, do Process until the operator stack is empty. The values left in the operand stack is our final result.

Please see the walkthrough of an example below for more understanding.

Complete Code:

Output:

4

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________