Infix to Postfix Conversion

The program must accept an infix expression S and convert it to the corresponding postfix expression.

Boundary Condition(s):
3 <= Length of S <= 100

Example Input/Output 1:
Input:
A*B*(C+D)%R+F-G/H*J 

Output:
AB*CD+*R%F+GH/J*-

Example Input/Output 2:
Input:
a+b*(c^d-e)^(f+g*h)-i

Output:
abcd^e-fgh*+^*+i-

#include<iostream>
#include<string>
#include<stack>

using namespace std;
bool isOperand(char c) {
    return (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z');
}

bool isOperator(char c) {
    if (c == '(')
        return true;
    if (c == '%')
        return true;
    if (c == ')')
        return true;
    if (c == '+')
        return true;
    if (c == '-')
        return true;
    if (c == '*')
        return true;
    if (c == '/')
        return true;
    if (c == '^')
        return true;
    return false;
}

int prec(char c) {
    if (c == '+')
        return 3;
    if (c == '%')
        return 4;
    if (c == '-')
        return 3;
    if (c == '*')
        return 4;
    if (c == '/')
        return 4;
    if (c == '^')
        return 5;
    return -1;
}

string ItoP(string s) {
    int i, l = s.length();
    string postfix = "";
    stack < char > stack;
    for (i = 0; i < l; i++) {
        if (isOperand(s[i])) {
            postfix = postfix + s[i];
        }

        if (isOperator(s[i])) {
            if (stack.empty()) {
                stack.push(s[i]);
            } else {
                if (s[i] == '(') {
                    stack.push(s[i]);
                } else {
                    if (s[i] == ')') {
                        while (stack.top() != '(') {
                            postfix = postfix + stack.top();
                            stack.pop();
                        }
                        stack.pop();
                    } else if (prec(s[i]) > prec(stack.top()) || s[i] == '^') {
                        stack.push(s[i]);
                    } else {
                        while (!stack.empty() && stack.top() != '(' && prec(stack.top()) >= prec(s[i])) {
                            postfix = postfix + stack.top();
                            stack.pop();
                        }
                        stack.push(s[i]);
                    }
                }
            }
        }
    }
    while (!stack.empty()) {

        postfix = postfix + stack.top();
        stack.pop();

    }
    return postfix;
}

int main() {
    string s;
    cin >> s;
    cout << ItoP(s) << endl;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

More posts. You may also be interested in.