Convert Infix to Postfix in C++

Remember those pesky equations that baffled you in like 1st grade? Addition and subtraction along with their friends multiplication and division. Hey, you wanted to go play kick ball or chase that girl around the playground… not to hook up with her but to put dirt in her hair. Well, you probably learned to write your equations in infix form like 3 + 4 or 2 * 7. This makes it easy for us as humans to read and understand, but can be a bit of a pain for that simple calculator program you are trying to write. Now if we could convert those equations to postfix, we could then make things a bit simpler. So here I am going to show you a simple program, easy to modify and extend, but verbose enough to be easy to understand… right here on the Programming Underground!

Most examples on the net show you a simple program with a ton of complex algorithms or funky coding mixed up with a bunch of single letter variables to show you the concept. They do this to make it compact as well as being able to say “Look at my leet converter and it was only done in 10 lines!” That is all nice to show off to your friends, but leaves people learning out in the cold.

If you are not familiar with postfix format, think of it as taking the operators and moving them to after the operands they work on. Thus 3 + 4 would be 34+. The expression A * B + C / D would become A B * C D / +. This format is a bit easier to then parse and was designed to utilize a stack structure and reduce the need to access memory. This format is also known as “polish notation” and before you ask, yes there is a prefix notation too.

The idea behind the conversion is to again, utilize a stack and a string. By looping through the input expression and evaluating each character as we go, we can decide to either put the character on the stack of operators or tack it onto a string we build as we go. In certain situations we consider operator precedence (which one is more important) to decide what needs to be taken off the stack and placed back on. I suggest you quickly review which operators have precedence of others in C++ before continuing.

In the example below I have created 3 simple helper functions to evaluate some characters and then our main function which will simply loop through our expression and use the helpers to figure out what to do with them. This program handles +, -, * and / but could easily be extended to handle any binary operator (that is an operator that works on two values or operands). + is a binary operator because when you write 2 + 4, it is working on adding two values… 2 and 4.

So we have one function that first checks if the character is an operator. It is a simple true/false function. We also have one that checks if it is an operand. If it is not an operator or parenthesis, it is assumed to be an operand. Lastly we have a helper function that compares operators to quickly decide which one has higher precedence. It takes in two operator characters and essentially says that if the second operator has higher precedence than the first operator, say it is greater than. If not, it is less than. Otherwise they are equal. Not too bad to understand really.

Now that we have these three helper functions, all that is left is to run through the string the user enters and run through the conversion rules. If it is an operand, add it to the string. If it is an operator, we are going to check our operator stack and compare the value on the top of the stack. It compares our operator to the one on the stack, popping them off the stack and adding to the string until the stack is empty, an open parenthesis or of greater precedence.

After that, all that is left is test if it is a parenthesis. If it is opening parenthesis, we can push it right onto the stack. If it is a closing one, then we are going to keep popping off operators until we meet up with the opening one to form the match. The last bit checks that if our expression has been completely parsed and we still have operators left on the stack, pop them all off and put them on the string.

The result here is that the string “postFixString” will then have the final post fix version of the expression.

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


// Simply determine if character is one of the four standard operators.
bool isOperator(char character) {
    if (character == '+' || character == '-' || character == '*' || character == '/') {
        return true;
    }
    return false;
}


// If the character is not an operator or a parenthesis, then it is assumed to be an operand.
bool isOperand(char character) {
    if (!isOperator(character) && character != '(' && character != ')') {
        return true;
    }
    return false;
}


// Compare operator precedence of main operators.
// Return 0 if equal, -1 if op2 is less than op1, and 1 if op2 is greater than op1.
int compareOperators(char op1, char op2) {
    if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) { return -1; }
    else if ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/')) { return 1; }
    return 0;
}


int main()
{
    // Empty character stack and blank postfix string.
    stack<char> opStack;
    string postFixString = "";
	
    char input[100];

    // Collect input
    cout << "Enter an expression: ";
    cin >> input;

    // Get a pointer to our character array.
    char *cPtr = input;

    // Loop through the array (one character at a time) until we reach the end of the string.
    while (*cPtr != '\0') {
        // If operand, simply add it to our postfix string.
        // If it is an operator, pop operators off our stack until it is empty, an open parenthesis or an operator with less than or equal precedence.
        if (isOperand(*cPtr)) { postFixString += *cPtr; }
        else if (isOperator(*cPtr)) {
            while (!opStack.empty() && opStack.top() != '(' && compareOperators(opStack.top(),*cPtr) <= 0) {
                postFixString += opStack.top();
                opStack.pop();
            }
            opStack.push(*cPtr);
        }
        // Simply push all open parenthesis onto our stack
        // When we reach a closing one, start popping off operators until we run into the opening parenthesis.
        else if (*cPtr == '(') { opStack.push(*cPtr); } 
        else if (*cPtr == ')') {
            while (!opStack.empty()) {
                if (opStack.top() == '(') { opStack.pop(); break; }
                postFixString += opStack.top();
                opStack.pop();
            }
        }

        // Advance our pointer to next character in string.
        cPtr++;
    }

    // After the input expression has been ran through, if there is any remaining operators left on the stack
    // pop them off and put them onto the postfix string.
    while (!opStack.empty()) {
        postFixString += opStack.top();
        opStack.pop();
    }


    // Show the postfix string at the end.
    cout << "Postfix is: " << postFixString << endl;
    return 0;
}

As you can see this is a bit of a drawn out style of the setup. We probably could actually boil down the functions into more cryptic single line checks in the main algorithm, but I wanted to make it verbose enough to show those learning how this thing is working. The rest of the code is pretty self explanatory and commented to show the process. One tip to keep in mind is that before you pop an operator off the stack that you first add it to the string and then pop it off the stack. In c++ the function pop() doesn’t return the value from the stack like it may in other languages.

By looping through the string character by character, evaluating its type and then utilizing a stack to store away operators until after the operands we can create the postfix version of an expression. From there it can be easier to convert for a simple calculator application because the operators can then be evaluated simply from left to right.

I hope you find this useful. Thanks again for reading! 🙂