How do I convert an infix expression to a postfix expression and I am not able to get the expected output?

Question

I am trying to write a C++ program to convert infix expressions to prefix and postfix. Where did I go wrong?

How can I change code to delete parentheses at the last form (postfix)? Thanks for any help!

Input :

a*(b-c+d)/e

Output :

abc-d+*e/
/*a+-bcde

Constraints/Assumptions :

1. Expression is balanced.
2. The only operators used are +, -, *, /
3. Opening and closing brackets - ( ) - are used to impact precedence of operations.
4. + and - have equal precedence which is less than * and /. * and / also have equal precedence.
5. In two operators of equal precedence give preference to the one on left.
6. All operands are single-digit numbers/characters.

#include <cstring>
#include <ctype.h>
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int precedence(char ch) {
    if (ch == '+') {
        return (1);
    } else if (ch == '-') {
        return (1);
    } else {
        return (2);
    }
}

void preProcess(stack<string> &preS, char op) {
    string val2 = preS.top();
    preS.pop();
    string val1 = preS.top();
    preS.pop();
    string prev;
    prev = op + val1 + val2;
    preS.push(prev);
}

void postProcess(stack<string> &postS, char op) {
    string val2 = postS.top();
    postS.pop();
    string val1 = postS.top();
    postS.pop();
    string postv;
    postv = val1 + val2 + op;
    postS.push(postv);
}

void prefixPostfixEvaluation(string expr) {
    stack<string> preS;
    stack<string> postS;
    stack<char> opS;
    for (int i = 0; i < expr.length(); ++i) {
        char ch = expr.at(i);
        if (ch == '(') {
            opS.push(ch);
        } else if ((ch <= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') ||
                   (ch <= 'A' && ch >= 'Z')) {
            string s;
            s = ch;
            preS.push(s);
            postS.push(s);
        } else if (ch == ')') {
            while (opS.top() != '(') {
                char op = opS.top();

                preProcess(preS, op);
                postProcess(postS, op);
                opS.pop();
            }
            opS.pop();
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            while (opS.size() > 0 && precedence(ch) <= precedence(opS.top()) &&
                   opS.top() != '(') {
                char op = opS.top();

                preProcess(preS, op);
                postProcess(postS, op);
                opS.pop();
            }
            opS.push(ch);
        }
    }
    while (opS.size() > 0) {
        char op = opS.top();
        opS.pop();
        if (op == '(' || op == ')') {
            continue;
        } else {
            preProcess(preS, op);
            postProcess(postS, op);
        }
    }
    cout << preS.top() << endl;
    cout << postS.top();
}

int main() {
    string expr;
    getline(cin, expr);
    prefixPostfixEvaluation(expr);
}

Answer 1

Your condition to check if a character is an operand is wrong. Instead of :

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

It should be

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

A better way would be to directly use isalnum(ch) in the conditional statement (you have already included ctype header).

Complete (corrected) code can be found here.

Note : Prefer including C++ variants of header like <cctype> instead of <ctype.h>. Moreover, there is no need to include <cstring> when <string> is included. Also, please go through this thread : Why is “using namespace std;” considered bad practice?

You are expecting postfix version to appear on line 1 and the prefix version to appear on line 2. But in code you're printing in reverse order, change it if order matters to you.