Question

Using STL stack class, implement in C++ a function that converts an infix expression to postfix expression,

Answer 1

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

// declare necessary functions which are defined below
int priority(char c);
bool isOperator(char c);

int main() {
        string infix, postfix;
        cout << "Enter an infix expression: ";
        cin >> infix; // take input in infix string
        stack<char> s; // instantiate stack of char
        
        /* We iterate a loop from start to end of infix string and for each character we do the following:
         * 1. if the character is an operator or brackets we check if it is opening bracket then we add it to stack and if it is closing bracket then we pop elements from stack until
         * it becomes empty or we found an opening bracket from the stack.
         * 2. if the character is an operator we check its precedence (or priority) using priority function. precedence of operators are as follows : '^' > ( '/' = '*') > ('+' = '-')
         * We keeps on popping elements from stack and adding it in postfix expression until the priority of current character becomes greater than stack's top element
        */
        
        for(int i=0; i<infix.length(); i++) {
                // check if the character is operator or a bracket or not
                if(isOperator(infix[i])) {
                        // if opening bracket just push it in stack
                        if(infix[i] == '(')
                                s.push(infix[i]);
                        // if it is closing bracket then continuously pop elements from stack and add in postfix string until we encounter a opening bracket or stack is empty
                        else if(infix[i] == ')') {
                                while(s.size() > 0 && s.top() != '(') {
                                        postfix += s.top();
                                        s.pop();
                                }
                                // if stack is not empty and top element is an opening bracket pop it
                                if(s.top() == '(') {
                                        s.pop();
                                }
                        }
                        else {
                                // if the character is an operator than we check its precedence and pop element until its precedence becomes greater than the top element from stack or stack is empty
                                while(s.size() > 0 && priority(infix[i]) <= priority(s.top())) {
                                        postfix += s.top();
                                        s.pop();
                                }
                                s.push(infix[i]); // push current characater in stack
                        }
                }
                // if the character is not an operator or a bracket then just add it in postfix expression string
                else {
                        postfix += infix[i];
                }
        }
        // add the remaining elements in postfix string
        while(s.size() > 0) {
                postfix += s.top();
                s.pop();
        }
        // print the postfix expression
        cout << "Postfix expression is: " << postfix << endl;
        return 0;
}

// returns true if the character is an operator or a bracket else return false
bool isOperator(char c) {
        if(c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '(' || c == ')')
                return true;
        return false;
}

// returns the priority of operator
// priority of '+' and '-' is 0
// priority of '*' and '/' is 1
// priority of '^' is 2
// priority of any other char is -1
int priority(char c) {
        if(c == '+' || c == '-')
                return 0;
        else if(c == '*' || c == '/')
                return 1;
        else if(c == '^')
                return 2;
        else
                return -1;
}

Output is like this: