Tutorial 18

 Infix to PostFix:

#include <iostream>

#include <stack>

using namespace std;


// Function to check if a character is an operator

bool isOperator(char c) 

{

    return (c == '+' || c == '-' || c == '*'

     || c == '/' || c == '^');    

}


// Function to determine the precedence of an operator

int precedence(char c) {

    if (c == '^') {

        return 3;

    } else if (c == '*' || c == '/') {

        return 2;

    } else if (c == '+' || c == '-') {

        return 1;

    } else {

        return -1; // Not an operator

    }

}


// Function to convert infix expression to postfix expression

string InfixToPostfix(string infix) {

    stack<char> s;

    string postfix;


    for (int i = 0; i < infix.length(); i++) {

        char ch = infix[i];


        // If operand, append to postfix expression

        if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))

{

            postfix += ch;

        }


        // If opening parenthesis, push onto stack

        else if (ch == '(') {

            s.push(ch);

        }


        // If closing parenthesis, pop operators until opening parenthesis is encountered

        else if (ch == ')') {

            while (!s.empty() && s.top() != '(') {

                char temp = s.top();

                postfix += temp;

                s.pop();

            }

            if (!s.empty()) { // Ensure there's an opening parenthesis at the top

                s.pop();

            } else {

                // Missing opening parenthesis, invalid expression

                return "Invalid Expression";

            }

        }


        // If operator, compare precedence with stack top and append accordingly

        else if (isOperator(ch)) {

            if (s.empty()) {

                s.push(ch);

            } else {

                while (!s.empty() && precedence(ch) <= precedence(s.top())) {

                    char temp = s.top();

                    postfix += temp;

                    s.pop();

                }

                s.push(ch);

            }

        }

    }


    // Pop remaining operators from stack and append to postfix

    while (!s.empty()) {

        char temp = s.top();

        postfix += temp;

        s.pop();

    }


    return postfix;

}


int main() {

    string infix_exp, postfix_exp;

    cout << "Enter a Infix Expression: ";

    cin >> infix_exp;


    postfix_exp = InfixToPostfix(infix_exp);


    if (postfix_exp != "Invalid Expression") {

        cout << "POSTFIX EXPRESSION: " << postfix_exp << endl;

    } else {

        cout << postfix_exp << endl; // Print "Invalid Expression" if encountered

    }


    return 0;

}

Infix to PreFix:

#include <iostream>
#include <stack>
using namespace std;

// Function to check if a character is an operator
bool isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}

// Function to determine the precedence of an operator
int precedence(char c) {
    if (c == '^') {
        return 3;
    } else if (c == '*' || c == '/') {
        return 2;
    } else if (c == '+' || c == '-') {
        return 1;
    } else {
        return -1; // Not an operator
    }
}

// Function to reverse a string
string reverseString(string str) {
    int n = str.length();
    string reversed;
    for (int i = n - 1; i >= 0; i--) {
        reversed += str[i];
    }
    return reversed;
}

// Function to convert infix expression to prefix expression
string InfixToPrefix(string infix) {
    // Reverse the infix expression
    string reversedInfix = reverseString(infix);

    // Use a stack to handle operators
    stack<char> s;
    string prefix;

    // Process the reversed infix expression
    for (int i = 0; i < reversedInfix.length(); i++) {
        char ch = reversedInfix[i];

        // If operand, append to prefix expression (reversed order)
        if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
            prefix = ch + prefix; // Prepend to the beginning
        }

        // If opening parenthesis, push onto stack
        else if (ch == ')') {
            s.push(ch);
        }

        // If closing parenthesis, pop operators until opening parenthesis is encountered
        else if (ch == '(') {
            while (!s.empty() && s.top() != ')') {
                char temp = s.top();
                prefix = temp + prefix; // Prepend to the beginning
                s.pop();
            }
            if (!s.empty()) { // Ensure there's an opening parenthesis at the top
                s.pop();
            } else {
                // Missing opening parenthesis, invalid expression
                return "Invalid Expression";
            }
        }

        // If operator, compare precedence with stack top and append accordingly
        else if (isOperator(ch)) {
            if (s.empty()) {
                s.push(ch);
            } else {
                while (!s.empty() && precedence(ch) <= precedence(s.top())) {
                    char temp = s.top();
                    prefix = temp + prefix; // Prepend to the beginning
                    s.pop();
                }
                s.push(ch);
            }
        }
    }

    // Pop remaining operators from stack and append to prefix (reversed order)
    while (!s.empty()) {
        char temp = s.top();
        prefix = temp + prefix; // Prepend to the beginning
        s.pop();
    }

    // Reverse the final prefix expression (to get the correct order)
    return reverseString(prefix);
}

int main() {
    string infix_exp, prefix_exp;
    cout << "Enter a Infix Expression: ";
    cin >> infix_exp;

    prefix_exp = InfixToPrefix(infix_exp);

    if (prefix_exp != "Invalid Expression") {
        cout << "PREFIX EXPRESSION: " << prefix_exp << endl;
    } else {
        cout << prefix_exp << endl; // Print "Invalid Expression" if encountered
    }

    return 0;
}


PostFix to Infix:


#include <iostream>
#include <stack>
using namespace std;

// Function to check if a character is an operand
bool isOperand(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

// Function to convert postfix expression to infix expression
string PostfixToInfix(string postfix) {
    stack<string> s;

    for (int i = 0; i < postfix.length(); i++) {
        char ch = postfix[i];

        // If operand, push it onto the stack as a string
        if (isOperand(ch)) {
            string operand(1, ch);
            s.push(operand);
        }

        // If operator, pop two operands, append the operator in the middle, and push the result back
        else {
            if (s.size() < 2) {
                return "Invalid Expression";
            }

            string op2 = s.top();
            s.pop();
            string op1 = s.top();
            s.pop();

            string expression = "(" + op1 + ch + op2 + ")";
            s.push(expression);
        }
    }

    // The final element in the stack is the infix expression
    if (s.size() != 1) {
        return "Invalid Expression";
    }

    return s.top();
}

int main() {
    string postfix_exp, infix_exp;
    cout << "Enter a Postfix Expression: ";
    cin >> postfix_exp;

    infix_exp = PostfixToInfix(postfix_exp);

    if (infix_exp != "Invalid Expression") {
        cout << "INFIX EXPRESSION: " << infix_exp << endl;
    } else {
        cout << infix_exp << endl; // Print "Invalid Expression" if encountered
    }

    return 0;
}


PostFix to PreFix:


#include<iostream>
#include<stack>

using namespace std;

bool isOperand(char c) {
  if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
    return true;
  } else {
    return false;
  }
}
string PostfixToPrefix(string postfix) 
{
  stack < string > s;
  for (int i = 0; i < postfix.length(); i++) 
  {
    if (isOperand(postfix[i])) {
      string op(1, postfix[i]);
      s.push(op);
    } else {
      string op1 = s.top();
      s.pop();
      string op2 = s.top();
      s.pop();
      s.push(postfix[i] + op2 + op1);
    }
  }
  return s.top();
}

int main() {

  string prefix, postfix;
  cout << "Enter a POSTFIX Expression :" << endl;
  cin >> postfix;
  cout << "POSTFIX EXPRESSION: " << postfix << endl;
  prefix = PostfixToPrefix(postfix);
  cout << endl << "PREFIX EXPRESSION: " << prefix;

  return 0;
}



PreFix to InFix:


#include <iostream>
#include <stack>

using namespace std;

bool isOperand(char c)
{
    if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
        return true;
    }
    else {
        return false;
    }
}

string PrefixToInfix(string prefix)
{
    stack<string> s;

    for (int i = prefix.length() - 1; i >= 0; i--)
     {
        if (isOperand(prefix[i])) 
        {
            string op(1, prefix[i]);
            //string op = prefix[i];
            s.push(op);
        }
        else {
            string op1 = s.top();
            s.pop();
            string op2 = s.top();
            s.pop();
            s.push("(" + op1 + prefix[i] + op2 + ")");
        }
    }
    return s.top();
}

int main()
{
    string infix, prefix;
    cout << "Enter a PREFIX Expression :" << endl;
    cin >> prefix;
    cout << "PREFIX EXPRESSION: " << prefix << endl;
    infix = PrefixToInfix(prefix);
    cout << endl
         << "INFIX EXPRESSION: " << infix;

    return 0;
}


PreFix to PostFix:


#include<iostream>
#include<stack>

using namespace std;

bool isOperand(char c) {
  if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
    return true;
  } else {
    return false;
  }
}

string PrefixToPostfix(string prefix) {
  stack < string > s;
  for (int i = prefix.length() - 1; i >= 0; i--) {
    if (isOperand(prefix[i])) {
      string op(1, prefix[i]);
      s.push(op);
    } else {
      string op1 = s.top();
      s.pop();
      string op2 = s.top();
      s.pop();
      s.push(op1 + op2 + prefix[i]);
    }
  }

  return s.top();
}

int main() {

  string prefix, postfix;
  cout << "Enter a PREFIX Expression :" << endl;
  cin >> prefix;
  cout << "PREFIX EXPRESSION: " << prefix << endl;
  postfix = PrefixToPostfix(prefix);
  cout << endl << "POSTFIX EXPRESSION: " << postfix;

  return 0;
}

No comments:

Post a Comment

Fell free to write your query in comment. Your Comments will be fully encouraged.