Postfix Evaluation Algorithm in Data Structures

Rumman Ansari   Software Engineer   2024-07-05 05:58:12   7125  Share
Subject Syllabus DetailsSubject Details
☰ TContent
☰Fullscreen

Infix notation is easier for humans to read and understand whereas for electronic machines like computers, postfix is the best form of expression to parse. We shall see here a program to convert and evaluate infix notation to postfix notation

We shall now look at the algorithm on how to evaluate postfix notation ?

Step 1 ? scan the expression from left to right 
Step 2 ? if it is an operand push it to stack 
Step 3 ? if it is an operator pull operand from stack and perform operation 
Step 4 ? store the output of step 3, back to stack 
Step 5 ? scan the expression until all operands are consumed 
Step 6 ? pop the stack and perform operation

Program

<span class="pln">
</span><span class="com">#include</span><span class="str">&lt;stdio.h&gt;</span><span class="pln"> 
</span><span class="com">#include</span><span class="str">&lt;string.h&gt;</span><span class="pln"> 

</span><span class="com">//char stack</span><span class="pln">
</span><span class="kwd">char</span><span class="pln"> stack</span><span class="pun">[</span><span class="lit">25</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="pln"> </span><span class="pun">-</span><span class="lit">1</span><span class="pun">;</span><span class="pln"> 

</span><span class="kwd">void</span><span class="pln"> push</span><span class="pun">(</span><span class="kwd">char</span><span class="pln"> item</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
   stack</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"> item</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="pln"> stack</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="com">//returns precedence of operators</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> precedence</span><span class="pun">(</span><span class="kwd">char</span><span class="pln"> symbol</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">symbol</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">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">break</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="kwd">break</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">4</span><span class="pun">;</span><span class="pln"> 
         </span><span class="kwd">break</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">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">break</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="com">//check whether the symbol is operator?</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> isOperator</span><span class="pun">(</span><span class="kwd">char</span><span class="pln"> symbol</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">symbol</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">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">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">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">1</span><span class="pun">;</span><span class="pln"> 
      </span><span class="kwd">break</span><span class="pun">;</span><span class="pln"> 
         </span><span class="kwd">default</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="pun">}</span><span class="pln"> 
</span><span class="pun">}</span><span class="pln"> 

</span><span class="com">//converts infix expression to postfix</span><span class="pln">
</span><span class="kwd">void</span><span class="pln"> convert</span><span class="pun">(</span><span class="kwd">char</span><span class="pln"> infix</span><span class="pun">[],</span><span class="kwd">char</span><span class="pln"> postfix</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"> i</span><span class="pun">,</span><span class="pln">symbol</span><span class="pun">,</span><span class="pln">j </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> 
   stack</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"> 
	
   </span><span class="kwd">for</span><span class="pun">(</span><span class="pln">i </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln">i</span><span class="pun">&lt;</span><span class="pln">strlen</span><span class="pun">(</span><span class="pln">infix</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">
      symbol </span><span class="pun">=</span><span class="pln"> infix</span><span class="pun">[</span><span class="pln">i</span><span class="pun">];</span><span class="pln"> 
		
      </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">isOperator</span><span class="pun">(</span><span class="pln">symbol</span><span class="pun">)</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> </span><span class="lit">0</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
         postfix</span><span class="pun">[</span><span class="pln">j</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> symbol</span><span class="pun">;</span><span class="pln"> 
         j</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">if</span><span class="pun">(</span><span class="pln">symbol </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">
            push</span><span class="pun">(</span><span class="pln">symbol</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">if</span><span class="pun">(</span><span class="pln">symbol </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">stack</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"> </span><span class="pun">{</span><span class="pln">
                  postfix</span><span class="pun">[</span><span class="pln">j</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> pop</span><span class="pun">();</span><span class="pln"> 
                  j</span><span class="pun">++;</span><span class="pln"> 
               </span><span class="pun">}</span><span class="pln"> 
					
               pop</span><span class="pun">();</span><span class="pln">   </span><span class="com">//pop out (. </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">if</span><span class="pun">(</span><span class="pln">precedence</span><span class="pun">(</span><span class="pln">symbol</span><span class="pun">)&gt;</span><span class="pln">precedence</span><span class="pun">(</span><span class="pln">stack</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">
                  push</span><span class="pun">(</span><span class="pln">symbol</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">precedence</span><span class="pun">(</span><span class="pln">symbol</span><span class="pun">)&lt;=</span><span class="pln">precedence</span><span class="pun">(</span><span class="pln">stack</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">
                     postfix</span><span class="pun">[</span><span class="pln">j</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> pop</span><span class="pun">();</span><span class="pln"> 
                     j</span><span class="pun">++;</span><span class="pln"> 
                  </span><span class="pun">}</span><span class="pln"> 
						
                  push</span><span class="pun">(</span><span class="pln">symbol</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="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">stack</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"> </span><span class="pun">{</span><span class="pln">
      postfix</span><span class="pun">[</span><span class="pln">j</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> pop</span><span class="pun">();</span><span class="pln"> 
      j</span><span class="pun">++;</span><span class="pln"> 
   </span><span class="pun">}</span><span class="pln"> 
	
   postfix</span><span class="pun">[</span><span class="pln">j</span><span class="pun">]=</span><span class="str">'\0'</span><span class="pun">;</span><span class="pln">  </span><span class="com">//null terminate string. </span><span class="pln">
</span><span class="pun">}</span><span class="pln"> 

</span><span class="com">//int stack</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> stack_int</span><span class="pun">[</span><span class="lit">25</span><span class="pun">];</span><span class="pln"> 
</span><span class="kwd">int</span><span class="pln"> top_int </span><span class="pun">=</span><span class="pln"> </span><span class="pun">-</span><span class="lit">1</span><span class="pun">;</span><span class="pln"> 

</span><span class="kwd">void</span><span class="pln"> push_int</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> item</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
   stack_int</span><span class="pun">[++</span><span class="pln">top_int</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> item</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_int</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
   </span><span class="kwd">return</span><span class="pln"> stack_int</span><span class="pun">[</span><span class="pln">top_int</span><span class="pun">--];</span><span class="pln"> 
</span><span class="pun">}</span><span class="pln"> 

</span><span class="com">//evaluates postfix expression</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> evaluate</span><span class="pun">(</span><span class="kwd">char</span><span class="pln"> </span><span class="pun">*</span><span class="pln">postfix</span><span class="pun">){</span><span class="pln">

   </span><span class="kwd">char</span><span class="pln"> ch</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="pln"> </span><span class="lit">0</span><span class="pun">,</span><span class="pln">operand1</span><span class="pun">,</span><span class="pln">operand2</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"> postfix</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">isdigit</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">
	     push_int</span><span class="pun">(</span><span class="pln">ch</span><span class="pun">-</span><span class="str">'0'</span><span class="pun">);</span><span class="pln">  </span><span class="com">// Push the operand </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="com">//Operator,pop two  operands </span><span class="pln">
         operand2 </span><span class="pun">=</span><span class="pln"> pop_int</span><span class="pun">();</span><span class="pln">
         operand1 </span><span class="pun">=</span><span class="pln"> pop_int</span><span class="pun">();</span><span class="pln">
			
         </span><span class="kwd">switch</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="kwd">case</span><span class="pln"> </span><span class="str">'+'</span><span class="pun">:</span><span class="pln">
               push_int</span><span class="pun">(</span><span class="pln">operand1</span><span class="pun">+</span><span class="pln">operand2</span><span class="pun">);</span><span class="pln">
               </span><span class="kwd">break</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">
               push_int</span><span class="pun">(</span><span class="pln">operand1</span><span class="pun">-</span><span class="pln">operand2</span><span class="pun">);</span><span class="pln">
               </span><span class="kwd">break</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">
               push_int</span><span class="pun">(</span><span class="pln">operand1</span><span class="pun">*</span><span class="pln">operand2</span><span class="pun">);</span><span class="pln">
               </span><span class="kwd">break</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">
               push_int</span><span class="pun">(</span><span class="pln">operand1</span><span class="pun">/</span><span class="pln">operand2</span><span class="pun">);</span><span class="pln">
               </span><span class="kwd">break</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="pun">}</span><span class="pln">
	
   </span><span class="kwd">return</span><span class="pln"> stack_int</span><span class="pun">[</span><span class="pln">top_int</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"> infix</span><span class="pun">[</span><span class="lit">25</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="str">"1*(2+3)"</span><span class="pun">,</span><span class="pln">postfix</span><span class="pun">[</span><span class="lit">25</span><span class="pun">];</span><span class="pln"> 
   convert</span><span class="pun">(</span><span class="pln">infix</span><span class="pun">,</span><span class="pln">postfix</span><span class="pun">);</span><span class="pln"> 
	
   printf</span><span class="pun">(</span><span class="str">"Infix expression is: %s\n"</span><span class="pln"> </span><span class="pun">,</span><span class="pln"> infix</span><span class="pun">);</span><span class="pln">
   printf</span><span class="pun">(</span><span class="str">"Postfix expression is: %s\n"</span><span class="pln"> </span><span class="pun">,</span><span class="pln"> postfix</span><span class="pun">);</span><span class="pln">
   printf</span><span class="pun">(</span><span class="str">"Evaluated expression is: %d\n"</span><span class="pln"> </span><span class="pun">,</span><span class="pln"> evaluate</span><span class="pun">(</span><span class="pln">postfix</span><span class="pun">));</span><span class="pln">
</span><span class="pun">}</span><span class="pln"> 
</span>

Output

If we compile and run the above program, it will produce the following result 

Infix expression is: 1*(5+3)
Postfix expression is: 153+*
Result is: 8
MCQ Available

There are 1 MCQs available for this topic.

1 MCQ

No Questions Data Available.
No Program Data.

Stay Ahead of the Curve! Check out these trending topics and sharpen your skills.