2
\$\begingroup\$

I'm doing a infix to postfix conversion. The code works, but here are some points I want to improve

1) In the line of

while ((!operators.empty())&&(order(operators.top()) >= order(token[0])))

If the condition order changes ( check the stack empty later), there'll be a segmentation fault (because I'm calling operators.top() which is NULL)

2) Convert from char to string using:

 string s(1, operators.top()); 

which I think constantly create a new variable s and delete it.

How to improve this code?

#include "Parser.h"
#include <sstream>
#include <algorithm>
#include <iterator>

using namespace std;

Parser::Parser()
{
    Postfix="";
    _source="";
    operators=std::stack<char>();
}

string Parser::postfix()
{
    return Postfix;
}

string Parser::source()
{
    return _source;
}

Parser& Parser::parse(string s)
{
    Postfix="";
    _source="";
    operators=std::stack<char>();

    _source=s;
    string token;

    istringstream iss (_source);
    while (iss >> token)
    {
        if (isdigit(token))
            Postfix.append(token).append(" ");

        if (isoperator(token))
        {
            if (operators.empty())
            {
                operators.push(token[0]);
            }
            else
            {
                // Pop until get the same order operator
                while ((!operators.empty())&&(order(operators.top()) >= order(token[0])))
                {
                    string s(1, operators.top());   
                    Postfix.append(s).append(" ");
                    operators.pop();
                }
                operators.push(token[0]);
            }
        }
        cout <<Postfix<<"\n";       
    }
    while(!operators.empty())
    {   
        string s(1, operators.top());   
        Postfix.append(s).append(" ");
        operators.pop();
    }
    return *this;
}

bool Parser::isdigit(const string &str)
{
    return str.find_first_not_of("-0123456789") == std::string::npos;
}

bool Parser::isoperator(const string &str)
{
    return (str=="+")||(str=="-")||(str=="*")||(str=="/");
}
int Parser::order(const char& c)
{
    if (c=='+')
        return 1;
    else if (c=='-')
        return 1;
    else if (c=='*')
        return 2;
    else if (c=='/')
        return 2;
    else
        return 0;
}
\$\endgroup\$
3
  • \$\begingroup\$ To improve it I would write it in a language designed for parsing. Have a look at flex and yacc(bison). \$\endgroup\$ Oct 3 '13 at 15:57
  • 1
    \$\begingroup\$ Are you trying to implement the Shunting Yard Algorithm? \$\endgroup\$ Oct 3 '13 at 16:01
  • \$\begingroup\$ yes, I'm implementing that algorithm. Rightnow is without paranthesis \$\endgroup\$ Oct 3 '13 at 16:16
1
\$\begingroup\$

If the condition order changes ( check the stack empty later), there'll be a segmentation fault (because I'm calling operators.top() which is NULL)

Calling top() on an empty queue is even worse then returning NULL. It is actually undefined behavior. Which means your code is broken.

This though:

while ((!operators.empty())&&(order(operators.top()) >= order(token[0])))

Is fine: The && operator evaluates the left hand side first and only if this evaluation returns true will it evaluates the right hand side. So the above expression is well formed and correct.

Convert from char to string using: which I think constantly create a new variable s and delete it.

Yes it creates a new variable s.

s will be destroyed(and its destructor called) when it goes out of scope (just like all variables are destroyed when they go out of scope). This is not a big deal.

Personally I would have used Flex/Bison to implement the parser.

\$\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.