4
\$\begingroup\$

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.
  1. If we reach the EOE, pop out every element from the stack, if there is any, and concatenate them as well.
\$\endgroup\$
5
  • \$\begingroup\$ How much did you test? It seems that your program crashes on the input string "1*2+3". \$\endgroup\$
    – Martin R
    May 29 at 15:51
  • \$\begingroup\$ @MartinR See the edit. Updated my code. It works fine now. \$\endgroup\$
    – Ultimate
    May 29 at 16:31
  • \$\begingroup\$ Are numbers with more than one digit allowed in the input string? Both "12+3" and "1+23" produce the same output "123+". \$\endgroup\$
    – Martin R
    May 29 at 16:35
  • \$\begingroup\$ @MartinR Yes, they are allowed. As we iterate over the infix string one character at a time it will not matter whether they are together or separated. And "12+3" and "1+23" will give the same output because if you follow the algorithm of the program you will find that '+' will be pushed into the stack and in both the cases is ejected out at last and then will be eventually added to the postfix string. Check this infix to postfix calculator for testing \$\endgroup\$
    – Ultimate
    May 29 at 16:47
  • 1
    \$\begingroup\$ That converter produces "12 3 +" and "1 23 +" where spaces separate the numbers and operators. \$\endgroup\$
    – Martin R
    May 29 at 17:19

2 Answers 2

6
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ post increment is a strange operation. it means: make a copy of the original, then increment the original, then return the copy - in your for loop, there is no need to make a copy of your int on every iteration. sure it's automatically optimized by the compiler, but why not just use the increment the original and return it-operator? makes your gcc 3.x -g builds run faster, if nothing else, and it does make a difference in other languages (for example it's not auto-optimized out in PHP<8 code) \$\endgroup\$
    – hanshenrik
    May 29 at 21:14
  • \$\begingroup\$ @hanshenrik - did you mean to put this comment here? It seems unrelated to my answer or to the question \$\endgroup\$
    – pm100
    May 30 at 4:03
  • 1
    \$\begingroup\$ I think you wanted to write plusOperator, minusOperator, ... in your example (4th paragraph) instead of operatorPlus, operatorMinus, etc. \$\endgroup\$
    – Heinzi
    May 30 at 8:25
  • \$\begingroup\$ @pm100 - What is the reason for using cout << "\n" rather than cout << endl ? \$\endgroup\$
    – Ultimate
    May 30 at 10:45
  • \$\begingroup\$ @Ultimate stackoverflow.com/questions/213907/stdendl-vs-n \$\endgroup\$
    – pm100
    May 30 at 16:39
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.