Question

Write a program in C++ to convert a text-file containing expressions (one per line) into post-fix expressions outputted to a file of your choice using a stack with one space between operators and variables (one letter variables) and/or constants (one digit constants). parentheses data

8*a+b-c+d/e

a+b*c+d/e+f ∧ g

a+b/4-d

a-b ∧ c/d+e

a/b*c/d*e

Answer 1

#ifndef __POSTFIX__H
#define __POSTFIX__H
#include<bits/stdc++.h>
using namespace std;
class Postfix
{
   public:
       //function that returns the precedence of char passed.
       int getPrecedence(char ch)
       {
           //if valid operators return value > 1
           if(ch == '+' || ch == '-')
           {
               return 1;
           }
           else if(ch == '*' || ch == '/')
           {
               return 2;
           }
           else if(ch == '^')
           {
               return 3;
           }
           else
           {
               //if invalid operator return -1
               return -1;
           }
       }
       //function that returns given charecter is valid operand
       bool isValidOperand(char ch)
       {
           //if is alphabet or digit return true.
           if(isalpha(ch) || isdigit(ch))
           {
               return true;
           }
           else
           {
               //return false.
               return false;
           }
       }
       //function that converts given infix expression into postfix.
       string convertToPostfix(string exp)
       {
           //stack to store the expression.
           stack<char> st;
           //push $ which says begin of the expression.
           st.push('$');
          
           //result of the infix to postfix.
           string res = "";
          
           //get length of expression.
           int len = exp.length();
           char ch;
           char ch2;
           int prec;
           //iterate whole expression
           for(int i =0;i<len;i++)
           {
               //store i_th char.
               ch = exp[i];
               //if valid operand add the ch to the result.
               if(isValidOperand(ch))
               {
                   res += ch;
                   res += " ";
               }
               else if(ch == '(')
               {
                   //if open parenthesis push ( to the stack
                   st.push(ch);
               }
               else if(ch == ')')
               {
                   //if ) parethesis
                   //till begining of the stack and top not open parenthsis
                   while(st.top() != '$' && st.top() != '(')
                   {
                       //pop top of the stack and add it to the result.
                       ch2 = st.top();
                       st.pop();
                       res += ch2;
                       res += " ";
                   }
                   //if top of the parenthsis not ( then pop the stack.
                   if(st.top() == '(')
                   {
                       ch2 = st.top();
                       st.pop();
                   }
                   else
                   {
                       //return invalid expressipn if top of the parenthesis is not ( after
                       //popping parameters.
                       return "Invalid expression: "+exp;
                   }
               }
               else
               {
                   //if not operand , (, ) then get the precedence.
                   prec = getPrecedence(ch);
                   //if prec == -1 then return invalid infix expressin
                   if(prec == -1)
                   {
                       return "Invalid Infix Expression : "+exp;
                   }
                   else
                   {
                       //while the top of the stack is not $ and precendence of the current ch
                       //less than top of tack
                       while(st.top() != '$' && getPrecedence(ch) <= getPrecedence(st.top()))
                       {
                           //add top of the stack char to the result.
                           ch2 = st.top();
                           st.pop();
                           res += ch2;
                           res += " ";
                       }
                       //push the i_th char.
                       st.push(ch);
                   }
               }
           }
           //append any characters in the stack.
           while(st.top() != '$')
           {
               ch2 = st.top();
               //if precendence == -1 and not valid operand
               if(getPrecedence(ch2) == -1 && !isValidOperand(ch2))
               {
                   //return invalid expression.
                   return "Invalid,s Infix Expression : "+exp;
               }
               //add the top of the stack to the char.
               st.pop();
               res += ch2;
               res += " ";
           }
           //before returning check for valid postfix expression or not.
          
           if(recognizePostfix(res))
           {
               return res;
           }
           else
           {
               return "Invalid expression: "+exp;
           }
          
       }
      
       //function recognizePostfix() that takes an string exprsssion
       //and returns if it is postfix expression or not.
       bool recognizePostfix(string exp)
       {
          
           //use a stack to store values.
           stack<double> st;
           //to store i_th char.
           char ch;
           //start from the expresion beginning.
           int len = exp.length();
           for(int i = 0; i< len; i++)
           {
               //get i_th char.
               ch = exp[i];
               if(ch == ' ')
               {
                   continue;
               }
               //if ch is operand push it to stack
               if(ch == ' ')
               {
                   continue;
               }
               if(isValidOperand(ch))
               {
                   st.push(ch - '0');
               }
               //if operator
               else if(getPrecedence(ch) != -1)
               {
                   //check if stack is empty if it is return false.
                   //because operator needs two operands if there are no operands
                   //then it is not valid
                   if(st.empty())
                   {
                       return false;
                   }
                   else
                   {
                       st.pop();
                   }
                   //after popping first operand try to pop second operand
                   if(st.empty())
                   {
                       //if stack empty return false.because we didn't have second operand to perform operation
                       return false;
                   }
                   else
                   {
                       //if second operand is there pop it.
                       st.pop();
                   }
                   //then push 1 because we have two operands to perform operation.
                   //operation results some value but we are just checking not evaluating
                   //so push 1 .
                   st.push(1);
               }
               else
               {
                   //if ch is neither operand or operator then it is a invalid character.
                   //so return false.
                   return false;
               }
           }
           //after whole operation there should be only one value in stack
           //if stack size returns 1
           if(st.size()==1)
           {
               //then return true.
               return true;
           }
           else
           {
               //if not return false.
               return false;
           }
       }
};
#endif

//------------ main.cpp ----------
#include "postfix.h"
#include<fstream>
//main function
int main()
{
   Postfix postfix;
   ifstream inp("inp.txt");
   if(inp == 0)
   {
       cout<<"Unable to read inp.txt file";
       return 0;
   }
   ofstream out("out.txt");
   if(out == 0)
   {
       cout<<"Unable to open out.txt file";
       return 0;
   }
  
   string line;
   string resExp;
   while(getline(inp,line))
   {
       resExp = postfix.convertToPostfix(line);
       out << "\nExpression: "<<line<<"\n";
       out << "Result: "<<resExp<<endl;
      
      
       cout << "\nExpression: "<<line<<"\n";
       cout << "Result: "<<resExp<<endl<<endl;
      
      
   }  
   return 0;
}

//--------- out.txt ----------

Expression: 8*a+b-c+d/e
Result: 8 a * b + c - d e / +

Expression: a+b*c+d/e+f^g
Result: a b c * + d e / + f g ^ +

Expression: a+b/4-d
Result: a b 4 / + d -

Expression: a-b^c/d+e
Result: a b c ^ d / - e +

Expression: a/b*c/d*e
Result: a b / c * d / e *

Expression: a/b*c/d*e++d
Result: Invalid expression: a/b*c/d*e++d
//---------inp.txt ------

8*a+b-c+d/e
a+b*c+d/e+f^g
a+b/4-d
a-b^c/d+e
a/b*c/d*e
a/b*c/d*e++d