9
\$\begingroup\$

I started with my own implementation of an algebraic calculator but ran into issues very early into the process. Then, I implemented the algorithm here. Please provide some inputs on areas where I can improve.

#include <iostream>
#include <stack>
#include <string>
#include <algorithm>

class infixProcessor{

public:
    infixProcessor(std::string input){
        inputString = input;
    }
private:
    std::string inputString;
    std::string postfixExpr;
    std::stack<char> stk;
    std::stack<std::string> postStk;



    bool isNumber (char inputValue){
        if (inputValue >=48 && inputValue <= 57) return true;
        else return false;
    }

    bool isOpenParen(char inputValue){
        if (inputValue == '(') return true;
        else return false;
    }

    bool isCloseParen(char inputValue){
        if (inputValue == ')') return true;
        else return false;
    }

    bool isOperator(char inputValue){
        if (inputValue == '+' || inputValue == '-') return true;
        else return false;
    }

    bool isSpace(char inputValue){
        if (inputValue == ' ') return true;
        else return false;
    }
public:
    void process(){


        inputString.erase(std::remove(inputString.begin(),inputString.end(),' '),inputString.end());
        std::string::iterator strIt;
        for (strIt = inputString.begin() ; strIt != inputString.end() ; strIt++){
            char currentValue = *strIt;
            if (isNumber(currentValue)){
                postfixExpr += currentValue;

                //Peek ahead, if next character is part of previous number
                while ( isNumber(*(strIt+1)) ){
                    postfixExpr += *(strIt+1);
                    strIt++;
                }

                postfixExpr += ' ';

            }
            else if (isOperator(currentValue)){
                while ( !stk.empty() && isOperator(stk.top()) ){
                    postfixExpr += stk.top();
                    postfixExpr += ' ';
                    stk.pop();
                }
                stk.push(currentValue);
            }
            else if (isOpenParen(currentValue)){
                stk.push(currentValue);
            }
            else if (isCloseParen(currentValue)){
                char temp = stk.top();
                stk.pop();
                while ( !isOpenParen(temp) ){
                    postfixExpr += temp;
                    postfixExpr += ' ';
                    temp = stk.top();
                    stk.pop();
                }
            }
        }

        while ( !stk.empty() ){
            char temp = stk.top();
            postfixExpr += temp;
            postfixExpr += ' ';
            stk.pop();
        }       
    }
private:
    int makeCalc(std::string num1, std::string num2, char op){
        if (op == '+') {
            return (std::stoi(num2) + std::stoi(num1));
        }
        else if (op == '-'){
            return (std::stoi(num2) - std::stoi(num1));
        }
    }
public:
    int postfixProcess(){
        std::string::iterator strIt;
        for (strIt = postfixExpr.begin() ; strIt != postfixExpr.end(); strIt++){
            char currentValue = *(strIt);

            if (isSpace(currentValue)) continue;

            else if (isNumber(currentValue)){
                std::string toPush;
                toPush += currentValue;
                while( isNumber(*(strIt+1)) ){
                    toPush+=*(strIt+1);
                    strIt++;
                }
                postStk.push(toPush);
            }

            else if (isOperator(currentValue)){
                std::string num1, num2;
                num1 = postStk.top();
                postStk.pop();
                num2 = postStk.top();
                postStk.pop();
                int result = makeCalc(num1, num2, currentValue);
                postStk.push(std::to_string(result));   
            }
        }
        return std::stoi(postStk.top());
    }
};

int main(){
    infixProcessor myProcessor("(1+(4+5+2)-3)+(6+8)");
    myProcessor.process();
    std::cout << myProcessor.postfixProcess() << std::endl;
    return 0;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The run-time performance is also not all that great. Any inputs on other data structures that I can use? \$\endgroup\$ Aug 9, 2015 at 22:21

3 Answers 3

6
\$\begingroup\$

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

Reconsider your object design

Right now, the declared public interface of infixProcessor looks like this:

public:
    infixProcessor(std::string input);
    void process();
    int postfixProcess();

This is an odd design because once the object has finished with a single input string, there is no way to get it to do anything else. Instead, I'd suggest a design like this:

public:
    static std::string toPostfix(const std::string &inputString);
    static int eval(const std::string &postfixString);

This would make the revised main look like this:

int main(){
    infixProcessor myProcessor;
    std::string postfix = myProcessor.toPostfix("(1+(4+5+12)-3)+(6+8)");
    std::cout << myProcessor.eval(postfix) << std::endl;
}

Or perhaps this:

int main(){
    std::cout << infixProcessor::eval(infixProcessor::toPostfix("(1+(4+5+12)-3)+(6+8)"))  << std::endl;
}

Minimize the scope of variables

The variable stk is only used within process and the variable postStk is only used within postfixProcess. This means that they could and should be local variables within those member functions rather than member data.

Make sure all paths return a value

The makeCalc routine returns the sum or difference of two operands if op is '+' or '-', respectively, but what if it's some other character? Either return an explicit value of some kind (perhaps 0?) or throw an exception.

Make functions static where practical

With a few small changes, every one of the member function of infixProcessor can be made static. Static member functions are appropriate when they need access to the representation of the class but needn't be called for a particular object. In this case, I'm advocating changing the class so that there is no data to access, in which case, using a namespace might be a better option.

Use const where practical

The makeCalc function does not alter either passed string, so those should be passed as const &:

static int makeCalc(const std::string &num1, const std::string &num2, char op);

Separate declaration from implementation

The code right now interleaves public and private functions and data and the implementation and declaration of member functions are the same. For others that might use the class (and for you to see it clearly yourself), separate the declaration from the implementation and also keep variables and functions each grouped together. For my suggested rewrite, the declaration might look like this:

class infixProcessor{
public:
    static std::string toPostfix(const std::string &inputString);
    static int eval(const std::string &postfixString);
private:
    static int makeCalc(const std::string &num1, const std::string &num2, char op);
    static bool isNumber (char inputValue);
    static bool isOpenParen(char inputValue);
    static bool isCloseParen(char inputValue);
    static bool isOperator(char inputValue);
    static bool isSpace(char inputValue);
};

Avoid needless conversions

The postStk variable is declared as std::stack<std::string> postStack but that then requires conversions back and forth between std::string and int. Just make it std::stack<int> and avoid a great number of needless conversions.

Use "range for" and simplify your code

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

int infixProcessor::eval(const std::string &postfixExpr){
    std::stack<int> postStk;
    bool inNum = false;
    int num = 0;
    for (char currentValue : postfixExpr) {
        if (std::isspace(currentValue))  {
            if (inNum) {
                postStk.push(num);
                inNum = false;
            }
        } else if (std::isdigit(currentValue)){
            if (inNum) {
                num = 10 * num + currentValue - '0';
            } else {
                num = currentValue - '0';
                inNum = true;
            }
        } else if (currentValue == '+' || currentValue == '-') {
            if (inNum) {
                inNum = false;
            } else {
                num = postStk.top();
                postStk.pop();
            }
            int num2 = postStk.top();
            postStk.pop();
            if (currentValue == '+') {
                postStk.push(num2+num);   
            } else {
                postStk.push(num2-num);   
            }
        }
    }
    return postStk.top();
}

The use of the "range for" eliminates the need for an explicit iterator, and the use of the boolean inNum allows the code to keep track of whether the code is in the middle of reading a multidigit number or not. Note too, that I have elected not to use any of the code's original classification functions such as isSpace and replacing them with standard functions such as std::isspace. The makeCalc routine is similarly replaced with the simple inlined numeric equivalent.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.

\$\endgroup\$
8
\$\begingroup\$

When comparing number in a text string you can use '0' and '9' etc...

bool isNumber (char inputValue){
    if (inputValue >=48 && inputValue <= 57) return true;
    else return false;
}

Is easier to read as:

bool isNumber (char inputValue){
    if (inputValue >= '0' && inputValue <= '9') return true;
    else return false;
}

Not only easier to read but the types are correct.

When you want to return true/false from an if expression better to just use the value of the expression.

bool isNumber (char inputValue){
    if (inputValue >= '0' && inputValue <= '9') return true;
    else return false;
}

Is easier to read as:

bool isNumber (char inputValue){
    return (inputValue >= '0' && inputValue <= '9');
}

Note if you are testing for a number it is more efficient to use the standard functions.

bool isNumber (char inputValue){
    return std::isdigit(inputValue);  // :-)
         //
         // This basically is inlined as an array lookup.
         //    return isdigitarray[inputValue];
}

Range based for.

for (strIt = inputString.begin() ; strIt != inputString.end() ; strIt++){

In C++11 we introduced a range based for. It works with any type that supports begin() and end()

for (auto const& value: inputString){
\$\endgroup\$
1
  • \$\begingroup\$ And since the last else is a return statement you could remove the else entirely. Maybe that's a safety check for if code is added to the function later but I'm more for not having needless code (I also am a C person and I am a participant and winner of the IOCCC so I keep down the keywords used though I'm certainly 'guilty' - if guilty is the right word - with having an else as the last statement in a function). Hardly matters though just adding it as a possibility (and saying that it's allowed). \$\endgroup\$
    – Pryftan
    Jun 14, 2020 at 15:55
2
\$\begingroup\$

At least in my opinion, many of the "traits-like" functions you've provided (e.g., isNumber, isOperator, etc.) don't really belong as part of the infixProcessor class itself.

These should be in a separate class--preferably one associated with the character type rather than the infixProcessor proper (and arguably they should probably be locale-specific as well).

Likewise, it would be preferable to decouple infix to postfix processing from the underlying storage--that is, infixProcessor shouldn't really depend directly on std::string. Rather, its input would ideally be specified as some sort of InputIterator or InputRange type or similar. Unfortunately, while there's a lot of work being put into adding ranges to C++, they're not there yet. Worse, iterators are clumsy to use.

That leaves you a choice: you can user iterators anyway, and live with their being a bit clumsy, or you could just pass a Container type as a generic parameter, and use a container of any type to which you can create an iterator.

As a much smaller point, you also want to use a member initializer list for initializing members, when possible.

template <class Container>
class infixProcessor { 
    Container inputString;
public:
    infixProcessor(Container const &input) : inputString(input) { }

I think I'd create an eval function template as well though--as Edward pointed out, most use of the infixProcessor class is basically as a single function, and it really makes the most sense to turn it into something that can be used like a function:

template <class Container>
int eval(Container const &input) { 
    infixProcess<Container> c(input);

    return(c.postfixProcess(c.process());
}

Then the rest of the code can use a simple interface:

auto x = eval("1+2*3/4");

auto y = eval(L"2*3+4-7");
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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