Infix: The expression in which the operator appears in between the operands is known as infix expression. For example, (a+b), where a and b are operands, + is an operator that appears between the operands a and b.
Example:
Infix: A*(B+C)/D, where A=2, B=4, C=3, D=2.
2*(4+3) /2 = 2* 7/2 = 2* 3.5 = 7.
To evaluate the infix expression here we use two stacks.
(i) Operand stack
(ii) Operator stack
Algorithm of infix evaluation:
Process:
Infix Evolution:
The infix expression should be scanned from left to right.
a. Push the operator into operator stack if operator stack is empty.
b. If the stack operator is not empty i.e. already one operator is present then
(i) If the current operator precedence is greater than or equal to the precedence of the operator present at the stack top of the operator stack, then push this current operator to the operator stack.
(ii) If the current operator precedence is less than the precedence of the operator present at the stack top of the operator stack then execute the above Process (as explained above) until the character’s precedence is less or the stack is not empty.
3. If the character is “(“, then push it onto the operator stack.
4. If the character is “)”, then execute the above Process (as explained above)
until the matching “(” is encountered in the operator stack. Now just pop out the “(“.
When the expression iteration is completed but the operator stack is not empty, due Process until the operator stack is empty.
The value left in the operand stack is our result.
Evolution of infix with an example:
Infix expression: 5/(5*(2+1))*2-10
Result: 4
TIME COMPLEXITY:
To evaluate infix expression, we have to scan n symbols.
So, the Time complexity of infix evaluation is O(n).
SPACE COMPLEXITY:
We require n stack to evaluate infix expression. So, space complexity is O(n).
Related
Contributed by