Question

Write a C++ program that converts an infix expression, which includes (, ), +, -, *, and / operations to postfix notation. The program should allow the user to enter an infix expression using lower case characters, then it will display the result of conversion on the screen. (Note: Use the STL stack class to accomplish the solution.).

Answer 1

SOLUTION:

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int precedence(char ch);
//This function is used to the precedence of the operators
//operator precedence is like + and - has same precedence
// * and / has same precedence and has greater than + and -
// braces has the highesht precedence than * and /

int precedence(char ch)
{

   if(ch == '+' || ch == '-')
   return 1;
else if(ch == '*' || ch == '/')
   return 2;
   return -1;
}
  
int main()
{
string s,output;
cout<<"Enter the infix Expression:";
//Read the infix expression
   cin>>s;
int len = s.length();
//Declare the stack
stack<char> stac;
for(int i = 0; i < len; i++)
{
// if the variable is from a to z append to the output
if(s[i] >= 'a' && s[i] <= 'z'){
   output+=s[i];
       }
       // if we encounter an ( push it to the stack
else if(s[i] == '(') {
   stac.push('(');   
       }
       // if we encounter ) pop all the data till the ( and append to the output and pop (
else if(s[i] == ')')
{
while(!stac.empty() && stac.top() != '(')
{
  
char c = stac.top();
               stac.pop();
               output += c;
}
stac.pop();
}
// when we see the operator we need to check the precedence of the operator
// we have to follow three rules when we encounter an operator
//1. If the operator has equal precedence pop the operator from the stack and append to the output and push the encountered
//operator to the stack
//2. If we encounter an operator which is having the greater precedence than the encountered operator
//push it onto the stack
//3. if we encounter an operator which is having the less precedence than the encountered operator
//pop from the stack and append it onto the output and push the encountered operator
else{
while(!stac.empty() && precedence(s[i]) <= precedence(stac.top()))
{
char c = stac.top();
stac.pop();
output += c;
}
stac.push(s[i]);
}
  
}
//if we have completed the parsing the data we need to pop all the data from stack and append it to the output
while(!stac.empty())
{
char c = stac.top();
stac.pop();
output += c;
}
//print the final output
cout <<"PostFix expression is :"<< output;
return 0;
}

EXPLANATION:

Rules of the stack :

1. If the operator has equal precedence pop the operator from the stack and append to the output and push the encountered
operator to the stack
2. If we encounter an operator which is having the greater precedence than the encountered operator push it onto the stack
3. if we encounter an operator which is having the less precedence than the encountered operator
pop from the stack and append it onto the output and push the encountred operator

Precedence Rules:

1 operator precedence is like + and - has the same precedence
2 * and / has the same precedence and has greater than + and -
3 braces have the highest precedence than * and /

SOURCE CODE

OUTPUT: