Infix to Postfix Converter in C++

Question

I have written a program to convert an infix expression to postfix with the help of infix2postfix() function. Please review my code and suggest ways to make it simpler and more readable.

Code:

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

int isOperator(char x)
{
    return (x == '-' || x == '+' || x == '/' || x == '*');
}

int precedenceOperator(char x)
{
    if (x == '+' || x == '-')
    {
        return 1;
    }
    else if (x == '/' || x == '*')
    {
        return 2;
    }

    return 0;
}

string infix2Postfix(string infix)
{
    int i = 0;
    stack<char> lobby;
    string postfix;
    if (infix.size() == 0)
    {
        return "";
    }
    while (infix[i] != '\0')
    {
        if (!isOperator(infix[i]))
        {
            postfix = postfix + infix[i];
            i++;
        }
        else
        {
            while (!lobby.empty() && precedenceOperator(infix[i]) <= precedenceOperator(lobby.top()))
            {
                postfix += lobby.top();
                lobby.pop();
            }
            lobby.push(infix[i]);
            i++;
        }
    }
    while (!lobby.empty())
    {
        postfix = postfix + lobby.top();
        lobby.pop();
    }
    return postfix;
}

Implementation:

int main()
{
    string infix;
    cout << "WELCOME TO INFIX TO POSTFIX CONVERTER: " << endl;
    cout << "Enter your Infix Expression: ";
    getline(cin, infix);
    string postfix = infix2Postfix(infix);
    cout << "The Postfix Expression is : " << postfix << endl;
    return 0;
}

Logic:

1. We create a string variable that will hold our postfix expression. Now, start iterating over our infix string. If we receive an operand, concatenate it to the postfix string. Else if we encounter an operator, proceed with the following steps:

• Keep in account the operator and its relative precedence. (We have 4 operators where '/' and '*' hold more precedence than '+' and '-')
• If either the stack is empty or its topmost operator has lower relative precedence, push this operator inside the stack.
• Else, keep popping operators from the stack and concatenate them to the postfix expression until the topmost operator becomes weaker in precedence relative to the current operator.

2. If we reach the EOE, pop out every element from the stack, if there is any, and concatenate them as well.

Answer 1

std::getline is defined in the include <string>, which you do not have, so the code doesn't compile for me.

Don't do using namespace std; see https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice.

int isOperator(char x) should be a bool since it is a logical test.

int precedenceOperator(char x) should be called operatorPrecedence(), otherwise it sounds like an operator type (operatorPlus, operatorMinus, operatorPrecedence).

I would change these lines:

if (infix.size() == 0)
{
    return "";
}
while (infix[i] != '\0')
{

To:

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

The redundant empty test is removed, the definition of i is moved to where it is first needed and scoped as needed. The intent is clear. If you do not do that then the 2 i++ are redundant; just one at the end of that while is needed.

Even better is the more modern:

for(char ch : infix)
{
    if (!isOperator(ch))
    {

Etc, replacing all infix[i] by ch.

cout << endl is generally considered a bad idea nowadays, use cout << '\n' instead.

---

Comments on logic:

In a comment you stated that it is correct that "12+3" and "1+23" both produce 123+.

I 100% disagree. The usual purpose of an infix to postfix handler is to create input to a calculation engine. Putting 123+ into a calculation engine will never produce 15 or 24 (the correct answers to the input). This whole problem stems from you treating this as a simple string problem rather than a deeper (and more interesting) problem of parsing. I suggest that you go the whole way and add a postfix calculator after the conversion. You will end up with a better solution.

Ie, you should see IO like this:

WELCOME TO INFIX TO POSTFIX CONVERTER:
Enter your Infix Expression: 1 + 23
Converted is : 1, 23, +
Result: 24

You never declare any input invalid, for example "1+5 /" is returned as "15 /+". Instead of nonsense in produces nonsense out, you should produce an error. Again a deeper parsing would fix this.

You do not reject characters that are not whitespace, digits or operators.

Answer 2

Here are some ideas that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Use the appropriate headers

This code includes <cstring> which it doesn't need and omits <string> which it does need. Strive to have all of the appropriate #includes in your code.

Use const references where practical

The code currently declares its infix2Postfix function like so:

std::string infix2Postfix(std::string infix)

This has two problems. First it passes by value, so a new std::string is created on every call. This is wasteful of both time and memory. Second, it should actually be a const reference, since the string is not actually modified by the function.

Handle multidigit numbers

Right now, the program does not correctly handle multidigit numbers. For instance, I think you can easily see that these four infix expressions should produce different results if evaluated:

22+11*3
221+1*3
2+211*3
2+2*113

Unfortunately, your current program produces 22113*+ for all four which is clearly not correct.

Write some test code

More testing would help identify bugs. I wrote this little class to help test your code:

class Tester {
    std::string input;
    std::string expected;
public:
    Tester(const std::string& input, const std::string& output) : input{input}, expected{output} {}
    friend std::ostream& operator<<(std::ostream& out, const Tester& t) {
        auto output{infix2Postfix(t.input)};
        return out << (output == t.expected ? "OK " : "BAD")
            << "\t\"" << t.input << "\" ==> \"" 
            << output << "\", expected \"" << t.expected << '\"';
    }
};

That can conveniently be used in main like this:

int main()
{
    const std::array<Tester, 1> tests{{
        {"2+1*3", "213*+" },
    }};

    std::copy(tests.begin(), tests.end(), std::ostream_iterator<Tester>(std::cout, "\n"));
}

Use common C++ idioms

A few places in this code have a construct like this:

postfix = postfix + infix[i];

This is more compactly and clearly expressed using this common C++ idiom:

postfix += infix[i];

Now it's easy to see at a glance that we're appending a character.

Use "range for" and simplify your code

Here is an alternative implementation for your infix2Postfix() routine:

std::string infix2Postfix(const std::string& infix)
{
    std::string lobby{};
    std::string postfix{};
    for (auto ch : infix) {
        if (isOperator(ch)) {
            while (!lobby.empty() && precedenceOperator(ch) <= precedenceOperator(lobby.back())) {
                postfix += lobby.back();
                lobby.pop_back();
            }
            lobby.push_back(ch);
        } else { 
            postfix += ch;
        }
    }
    std::reverse(lobby.begin(), lobby.end());
    return postfix + lobby;
}

This uses a "range for" to simplify the loop and eliminate the i variable. Note that I've also changed from a std::stack to a std::string and eliminated the special case testing for an empty string or an empty stack. We can do this by simply always returning the string with the appended stack; if they are empty, this will also be an empty string.

Use the appropriate return type

The isOperator() simply returns a boolean value. It should be declared that way.

Consider reducing redundant code

It's probably not going to make a huge difference in this code, but the isOperator() and precedenceOperator() functions are somewhat redundant. That is, one could define isOperator() like this:

bool isOperator(char x) { return precedenceOperator(x); }

Also, I don't much like precedenceOperator as a name and would suggest just precedence.

This suggests that the isOperator function probably isn't really needed at all. Here's a rewrite of the loop shown above:

for (auto ch : infix) {
    auto p{precedence(ch)};
    if (p) {
        while (!lobby.empty() && p <= precedence(lobby.back())) {
            postfix += lobby.back();
            lobby.pop_back();
        }
        lobby.push_back(ch);
    } else { 
        postfix += ch;
    }
}

Consider error checking

An unbalanced string might be input, such as "3*" which has a binary operator but only a single item on the stack. A useful extension to your program might be to check for this condition and also to check for invalid characters in the input string.

Answer 3

This is more of an architectural review

Separate parsing, memory representation and output.

In order to make the program extensible, testable and more readable you might want to separate parts of it in dedicated functions or classes.

The algorithm can be logically divided in 2 steps and 3 'components'.

The steps:

1. Parsing of a string representation of an infix expression into a generic memory representation.
2. Conversion of the generic expression to a string representing the same postfix expression.

In order to do this we will need to define an internal representation structure.

Use polymorphism

Polymorphism and a nice class hierarchy are very good at representing generic expressions, this is one of the cases where it really works well. In our case we will just need one class for each operator, all of them can extend a class that define the 2 operands and one class to represents the actual numbers.

class Expression {}

class BinaryOp : public Expression {
  char opChar;
  Expression * l;
  Expression * r;
}

class Add : public BinaryOp {[...]}
class Sub : public BinaryOp {[...]}
class Mul : public BinaryOp {[...]}
class Div : public BinaryOp {[...]}

class Num : public Expression {
  int value;
}

This class hierarchy can represent any expression in a tree-like data structure. Each binary operator can have expression as children; Expressions can be other operators or a number.

In the Expression class we can now define our public interface:

class Expression {
  public:
    static Expression * fromInfix( const std::string & infixExpString );
    virtual std::string toPostFix() const = 0;
}

The implementation of toPostFix() is trivial if we take advantage of polymorphism and the tree-like structure. It is a recursive visit of the tree.

For binary operands:

return l.toPostFix() + " " + r.toPostFix() + " " + operatorChar;

For Literals:

return std::to_string(value);

The implementation of fromInfix( const std::string & infixExpString ) is more complex but it is not much different from your existing code, you just need to create an expression instead of outputting the postfix string directly.

The advantage of an approach like this is that it is easily extensible without needing heavy refactor or code duplication. It would be very easy for example to implement an "evaluate" method in the expression interface that actually calculate the value of the function.

virtual Expression * execute() const = 0;

or implement different input and output methods:

 static Expression * fromInfix( const std::string &  );
 static Expression * fromPostfix( const std::string &  );
 static Expression * fromPrefix( const std::string &  );

and:

virtual std::string toInfix() const = 0;
virtual std::string toPrefix() const = 0;
virtual std::string toPostFix() const = 0;

And experiment with pattern that facilitate this kind of architecture like Visitor

It is also easier to test sub part of the process: parsing and printing.

This is an example code with the classes a little bit more fleshed out:

class Expression {
public:
    virtual ~Expression() {};

    static Expression * fromInfixExp( const std::string & infixExp){
        //TODO: Parse string and build proper expression-tree structure
        // INPUT  -> 1 + 2 * 4
        // OUTPUT -> new Add(new Num(1), new Mul(new Num(2), new Num(4)));
        return nullptr;
    }

    virtual std::string toPostfixExp() const = 0;
};

class BinaryOp : public Expression {
public:
    BinaryOp(char _opChar, Expression * _l, Expression * _r ) :
        opChar(_opChar),
        l(_l),
        r(_r)
    {}

    ~BinaryOp() override {
        delete l;
        delete r;
    }

protected:
    char opChar;
    Expression * l;
    Expression * r;

public:
    std::string toPostfixExp() const override {
        return l->toPostfixExp() + " " + r->toPostfixExp() + " " + opChar;
    };
};

class Add : public BinaryOp {
public:
    Add( Expression * _l, Expression * _r ) : BinaryOp('+', _l, _r) {}
};

// TODO: Implement other operators
// class Sub : public BinaryOp {
// class Mul : public BinaryOp {
// class Div : public BinaryOp {
// class Mod : public BinaryOp { etc...

class Num : public Expression {
protected:
    int value;

public:
    Num( int v ) : value(v) {}

    std::string toPostfixExp() const override {
        return std::to_string(value);
    };
};

int main(int , char *argv[]) {
    std::unique_ptr<Expression> e(Expression::fromInfixExp(argv[1]));
    std::cout << e->toPostfixExp() << std::endl;
}