Conversion of infix expression to postfix expression
Problem Statement : Conversion of infix
expression to postfix expression
Theory : Infix Expression: Notation in which, the
operator comes in-between its operands.
Example: (a+b)*c
Representation of postfix expression is : abc+*
Infix to postfix operation uses following algorithm:
Algorithm:
Step 1: Scan the given string from left to right.
Step 2: Initialize an empty stack
Step 3: If the scanned character is operand, add
it to the postfix string
Step 4: If the scanned character is operator and
if the stack is empty add it to the stack, else compare the operator
with the present operator in the stack. If the present operator is
having higher priority then remove it from the stack and add to
postfix array else push the new operator at the next position into
the stack.
Step 5: Repeat these steps till all the
characters get scanned.
Step 6: At the end pop all the operators from the
stack and add them to the postfix array.
Steps to perform the operation of conversion :
((a+b)*c)
Symbol
|
Stack
|
Postfix Array
|
(
|
(
|
|
(
|
((
|
|
A
|
((
|
a
|
+
|
((+
|
a
|
B
|
((+
|
ab
|
)
|
((+)
|
ab
|
*
|
(*
|
ab+
|
C
|
(*
|
ab+c
|
)
|
(*)
|
ab+c
|
|
Empty
|
ab+c*
|
In this example, the expression from inner bracket is
converted into postfix format i.e. ab+ and then the outer bracket is
consider and the final result is ab+c*.
Questions:
- What is operator precedence order?
- Explain the need of conversion from infix to prefix.
- What are the steps to convert an expression from infix to prefix?
- write an expression with 5 operands in all forms that is prefix,infix and postfix form.
Comments
Post a Comment