Infix to Postfix Conversion: Algorithm and Examples
☰Fullscreen
Table of Content:
Procedure for Postfix Conversion
| 1. | Scan the Infix string from left to right. |
| 2. | Initialize an empty stack. |
| 3. | If the scanned character is an operand, add it to the Postfix string. |
| 4. | If the scanned character is an operator and if the stack is empty push the character to stack. |
| 5. | If the scanned character is an Operator and the stack is not empty, compare the precedence of the character with the element on top of the stack. |
| 6. | If top Stack has higher precedence over the scanned character pop the stack else push the scanned character to stack. Repeat this step until the stack is not empty and top Stack has precedence over the character. |
| 7. | Repeat 4 and 5 steps till all the characters are scanned. |
| 8. | After all characters are scanned, we have to add any character that the stack may have to the Postfix string. |
| 9. | If stack is not empty add top Stack to Postfix string and Pop the stack. |
| 10. | Repeat this step as long as stack is not empty. |
Algorithm for Postfix Conversion
S:stack while(more tokens) x<=next token if(x == operand) print x else while(precedence(x)<=precedence(top(s))) print(pop(s)) push(s,x) while(! empty (s)) print(pop(s))
Conversion To Postfix
EXAMPLE:
A+(B*C-(D/E-F)*G)*H
| Stack | Input | Output |
|---|---|---|
| Empty | A+(B*C-(D/E-F)*G)*H | - |
| Empty | +(B*C-(D/E-F)*G)*H | A |
| + | (B*C-(D/E-F)*G)*H | A |
| +( | B*C-(D/E-F)*G)*H | A |
| +( | *C-(D/E-F)*G)*H | AB |
| +(* | C-(D/E-F)*G)*H | AB |
| +(* | -(D/E-F)*G)*H | ABC |
| +(- | (D/E-F)*G)*H | ABC* |
| +(-( | D/E-F)*G)*H | ABC* |
| +(-( | /E-F)*G)*H | ABC*D |
| +(-(/ | E-F)*G)*H | ABC*D |
| +(-(/ | -F)*G)*H | ABC*DE |
| +(-(- | F)*G)*H | ABC*DE/ |
| +(-(- | F)*G)*H | ABC*DE/ |
| +(-(- | )*G)*H | ABC*DE/F |
| +(- | *G)*H | ABC*DE/F- |
| +(-* | G)*H | ABC*DE/F- |
| +(-* | )*H | ABC*DE/F-G |
| + | *H | ABC*DE/F-G*- |
| +* | H | ABC*DE/F-G*- |
| +* | End | ABC*DE/F-G*-H |
| Empty | End | ABC*DE/F-G*-H*+ |
Infix to postfix implementation in c
<span class="pln"> </span><span class="com">#include</span><span class="pln"> </span><span class="str"><stdio.h></span><span class="pln"> </span><span class="com">#include</span><span class="pln"> </span><span class="str"><conio.h></span><span class="pln"> </span><span class="com">#include</span><span class="pln"> </span><span class="str"><ctype.h></span><span class="pln"> </span><span class="com">#define</span><span class="pln"> SIZE </span><span class="lit">50</span><span class="pln"> </span><span class="kwd">char</span><span class="pln"> s</span><span class="pun">[</span><span class="pln">SIZE</span><span class="pun">];</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> top</span><span class="pun">=-</span><span class="lit">1</span><span class="pun">;</span><span class="pln"> push</span><span class="pun">(</span><span class="kwd">char</span><span class="pln"> elem</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> s</span><span class="pun">[++</span><span class="pln">top</span><span class="pun">]=</span><span class="pln">elem</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">char</span><span class="pln"> pop</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">return</span><span class="pun">(</span><span class="pln">s</span><span class="pun">[</span><span class="pln">top</span><span class="pun">--]);</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> pr</span><span class="pun">(</span><span class="kwd">char</span><span class="pln"> elem</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">switch</span><span class="pun">(</span><span class="pln">elem</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">case</span><span class="pln"> </span><span class="str">'#'</span><span class="pun">:</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">case</span><span class="pln"> </span><span class="str">'('</span><span class="pun">:</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">case</span><span class="pln"> </span><span class="str">'+'</span><span class="pun">:</span><span class="pln"> </span><span class="kwd">case</span><span class="pln"> </span><span class="str">'-'</span><span class="pun">:</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="lit">2</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">case</span><span class="pln"> </span><span class="str">'*'</span><span class="pun">:</span><span class="pln"> </span><span class="kwd">case</span><span class="pln"> </span><span class="str">'/'</span><span class="pun">:</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="lit">3</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> main</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">char</span><span class="pln"> infx</span><span class="pun">[</span><span class="lit">50</span><span class="pun">],</span><span class="pln">pofx</span><span class="pun">[</span><span class="lit">50</span><span class="pun">],</span><span class="pln">ch</span><span class="pun">,</span><span class="pln">elem</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> i</span><span class="pun">=</span><span class="lit">0</span><span class="pun">,</span><span class="pln">k</span><span class="pun">=</span><span class="lit">0</span><span class="pun">;</span><span class="pln"> </span><span class="com">//clrscr();</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"\n\nRead the Infix Expression ? "</span><span class="pun">);</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%s"</span><span class="pun">,</span><span class="pln">infx</span><span class="pun">);</span><span class="pln"> push</span><span class="pun">(</span><span class="str">'#'</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">while</span><span class="pun">(</span><span class="pln"> </span><span class="pun">(</span><span class="pln">ch</span><span class="pun">=</span><span class="pln">infx</span><span class="pun">[</span><span class="pln">i</span><span class="pun">++])</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="str">'\0'</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">if</span><span class="pun">(</span><span class="pln"> ch </span><span class="pun">==</span><span class="pln"> </span><span class="str">'('</span><span class="pun">)</span><span class="pln"> push</span><span class="pun">(</span><span class="pln">ch</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">isalnum</span><span class="pun">(</span><span class="pln">ch</span><span class="pun">))</span><span class="pln"> pofx</span><span class="pun">[</span><span class="pln">k</span><span class="pun">++]=</span><span class="pln">ch</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="kwd">if</span><span class="pun">(</span><span class="pln"> ch </span><span class="pun">==</span><span class="pln"> </span><span class="str">')'</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">while</span><span class="pun">(</span><span class="pln"> s</span><span class="pun">[</span><span class="pln">top</span><span class="pun">]</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="str">'('</span><span class="pun">)</span><span class="pln"> pofx</span><span class="pun">[</span><span class="pln">k</span><span class="pun">++]=</span><span class="pln">pop</span><span class="pun">();</span><span class="pln"> elem</span><span class="pun">=</span><span class="pln">pop</span><span class="pun">();</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">while</span><span class="pun">(</span><span class="pln"> pr</span><span class="pun">(</span><span class="pln">s</span><span class="pun">[</span><span class="pln">top</span><span class="pun">])</span><span class="pln"> </span><span class="pun">>=</span><span class="pln"> pr</span><span class="pun">(</span><span class="pln">ch</span><span class="pun">)</span><span class="pln"> </span><span class="pun">)</span><span class="pln"> pofx</span><span class="pun">[</span><span class="pln">k</span><span class="pun">++]=</span><span class="pln">pop</span><span class="pun">();</span><span class="pln"> push</span><span class="pun">(</span><span class="pln">ch</span><span class="pun">);</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">while</span><span class="pun">(</span><span class="pln"> s</span><span class="pun">[</span><span class="pln">top</span><span class="pun">]</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="str">'#'</span><span class="pun">)</span><span class="pln"> pofx</span><span class="pun">[</span><span class="pln">k</span><span class="pun">++]=</span><span class="pln">pop</span><span class="pun">();</span><span class="pln"> pofx</span><span class="pun">[</span><span class="pln">k</span><span class="pun">]=</span><span class="str">'\0'</span><span class="pun">;</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"\n\nGiven Infix Expn: %s Postfix Expn: %s\n"</span><span class="pun">,</span><span class="pln">infx</span><span class="pun">,</span><span class="pln">pofx</span><span class="pun">);</span><span class="pln"> getch</span><span class="pun">();</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span>
Read the Infix Expression ? A+(B*C-(D/E-F)*G)*H Given Infix Expn: A+(B*C-(D/E-F)*G)*H Postfix Expn: ABC*DE/F-G*-H*+
No Questions Data Available.
No Program Data.