C++ Program to Convert Infix to Postfix Using Stack

• Previous
• Next

In this article, you will write a C++ program to convert infix expression to a postfix expression using stack operations.

Advertisements

This program is written using Turbo C++ compiler on a Windows 7 64-bit PC. You can use any other suitable C++ compiler and it will still work. Make sure to change the syntax according to the compiler you are using.

Problem Definition

The program requires infix expression as an input. Once the input is received, it will do following to convert the infix expression into a postfix expression. This program use a character stack.

Advertisements
• Receive the input expression with a ‘$’ sign at the end.
• Read the characters one at a time.
• If the character is alphabet, do not put on the stack, but print it.
• If the character is non-alphabet then put it on the stack, and print it if the priority is higher than the next character.
• If the character read is ‘(‘, print every thing from the stack until you reach ‘)’ character.
• Stack become empty, you continue with the rest of the expression.
• If you encounter a ‘$’ sign, the infix to postfix is completed.



Source Code – Infix to Postfix

/* C++ Program To Convert Infix Expression
To Postfix Expression */

#include  "iostream.h"
#include  "string.h"
#include  "ctype.h"
#include  "conio.h"
#include  "stdio.h"
#include  "math.h"

class ex1 {

  char str[50];

public:

  void input();
  int strprt(char);
  int expprt(char);
  void convert();
  };

//Class declaration ends here

void ex1::input() {

  cout << "Enter the Infix expression"<< endl;
  cout << "End with $ sign:"<< endl;
  cin >> str;
  }

int ex1::strprt(char c) {

  int pr;
  switch(c) {

    case '#':

      pr = -1;
      break;

    case '(':
    case ')':
      pr = 0;
      break;

    case '*':
    case '/':
      pr = 2;
      break;

   case '+':
   case '-':
      pr = 1;
      break;
   }

   // Switch-Case ends here

   return(pr);
   }

   int ex1::expprt(char c) {

     int pr;

     switch(c) {

       case '(':
	pr = 4;
	break;

       case ')':
	pr = 0;
	break;

       case '*':
       case '/':
	pr=2;
	break;

       case '+':
       case '-':
	pr = 1;
	break;
	}

       return(pr);
       }

   void ex1::convert() {

     int i = 0;
     int top = 0;

     char stk[50],item;

     while(str[i]!= '$') {

       item = str[i];

       if(isalpha(item)) {

	 cout<< item;

	 }
      else {

	 if(item == ')') {

	   while(stk[top]!='(') {


	     cout << stk[top];

	     --top;

	     }
	  --top;

	 }

	 else {

	   while((strprt(str[top])) > expprt(item)) {

	     cout << stk[top];

	     --top;
	   }

	++top;

	stk[top] = item;

	}
     }

     i++;

     }

   while(top >= 1) {

     cout << stk[top];

     --top;

     }
   }

   //Function convert ends here

   // Main Function

   void main() {

     ex1 ob;

     clrscr();

     ob.input();

     ob.convert();

     getch();

     }

Output – Infix to Postfix

Enter the Infix expression End with the ‘$’ sign:

(X+(Y*Z))/(X*Z)

Output:
XYZ*+XZ*/

• Previous
• Next