Infix to postfix conversion in C++

Question

Here is a program for conversion of an infix expression to a postfix expression using a stack. I would like to know how I could improve my checking for invalid input, make my code more expressive, and also improve the performance if possible.

I am using gcc 7.4.0. I can use C++17 if needed. This program compiles with C++11.

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <stdexcept>

class digitException : public std::runtime_error
{
    using std::runtime_error::runtime_error;
};

class unbalancedParentheses : public std::runtime_error
{
    using std::runtime_error::runtime_error;
};

inline bool isOpeningParenthesis(char c) {return c == '(';}
inline bool isClosingParenthesis(char c) {return c == ')';}

inline bool isOperator(char c) 
{
    return 
        (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}

void checkValidInfix(const std::string& expr)
{
    std::stack<char> parentheses;
    for(auto curr : expr) {
        if(isdigit(curr))
            throw digitException {"Digits not supported."};

        if(isOpeningParenthesis(curr))
            parentheses.push(curr);

        else if(isClosingParenthesis(curr)) {
            if(parentheses.empty()) 
                throw unbalancedParentheses {"Parentheses unbalanced."};
            parentheses.pop();
        }
    }
    if(!parentheses.empty())
        throw unbalancedParentheses {"Parentheses unbalanced."};
}

void getInfixExpression(std::istream& is, std::string& expr) {
    is >> expr;
    checkValidInfix(expr);
}

bool isHigherPrecedenceThan(char currSymbol, char onStack)
//Returns true if precedence of current symbol is higher than 
//the symbol on stack.
//False otherwise. False if something other than an operand is given.
{
    if(!isOperator(currSymbol) || !isOperator(onStack))
        return false;

    if(currSymbol == '+' && onStack == '+') return false;
    if(currSymbol == '+' && onStack == '-') return false;
    if(currSymbol == '+' && onStack == '*') return false;
    if(currSymbol == '+' && onStack == '/') return false;
    if(currSymbol == '+' && onStack == '^') return false;

    if(currSymbol == '-' && onStack == '+') return false;
    if(currSymbol == '-' && onStack == '-') return false;
    if(currSymbol == '-' && onStack == '*') return false;
    if(currSymbol == '-' && onStack == '/') return false;
    if(currSymbol == '-' && onStack == '^') return false;

    if(currSymbol == '*' && onStack == '+') return true;
    if(currSymbol == '*' && onStack == '-') return true;
    if(currSymbol == '*' && onStack == '*') return false;
    if(currSymbol == '*' && onStack == '/') return false;
    if(currSymbol == '*' && onStack == '^') return false;

    if(currSymbol == '/' && onStack == '+') return true;
    if(currSymbol == '/' && onStack == '-') return true;
    if(currSymbol == '/' && onStack == '*') return false;
    if(currSymbol == '/' && onStack == '/') return false;
    if(currSymbol == '/' && onStack == '^') return false;

    if(currSymbol == '^' && onStack == '+') return true;
    if(currSymbol == '^' && onStack == '-') return true;
    if(currSymbol == '^' && onStack == '*') return true;
    if(currSymbol == '^' && onStack == '/') return true;
    if(currSymbol == '^' && onStack == '^') return true;
}

std::string convertToPostfix(const std::string& infix)
{
    std::stack<char> operatorStack;
    std::string result;
    auto inputSymbol = infix.begin();

    while(inputSymbol != infix.end()) {
        char currSymbol = *inputSymbol;

        if(std::isalpha(currSymbol))
            result.push_back(currSymbol);

        else if(isOperator(currSymbol)) {
            if(operatorStack.empty() ||
                     isOpeningParenthesis(operatorStack.top()))
                operatorStack.push(currSymbol);

            else 
                if(isHigherPrecedenceThan(currSymbol, operatorStack.top()))
                    operatorStack.push(currSymbol);

                else {
                    while(!operatorStack.empty() && 
                    !isOpeningParenthesis(operatorStack.top()) &&
                    !isHigherPrecedenceThan(currSymbol, operatorStack.top())) {
                        result.push_back(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(currSymbol);
                }
        }

        else if(isOpeningParenthesis(currSymbol))
            operatorStack.push(currSymbol);

        else if(isClosingParenthesis(currSymbol)) {
            while(!isOpeningParenthesis(operatorStack.top())) {
                result.push_back(operatorStack.top());
                operatorStack.pop();
            }
            operatorStack.pop();
        }

        ++inputSymbol;
    }
    while(!operatorStack.empty()) {
        result.push_back(operatorStack.top());
        operatorStack.pop();
    }

    return result;
}


int main()
{
    try {
        std::string infixExpr;
        std::cout << "Enter Infix Expression: ";
        getInfixExpression(std::cin, infixExpr);
        std::cout << "Postfix Expression: " << convertToPostfix(infixExpr) 
            << "\n";
    }
    catch(const unbalancedParentheses& up) {
        std::cerr << up.what() << "\n";
    }
    catch(const digitException& de) {
        std::cerr << de.what() << "\n";
    }
}

Here are some examples :

Enter Infix Expression: a-b-c
Postfix Expression: ab-c-

Enter Infix Expression: a*b+c/g-h^j
Postfix Expression: ab*cg/+hj^-

Enter Infix Expression: a+b*c+(d*e+f)*g
Postfix Expression: abc*+de*f+g*+

Answer 1

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

Make sure all paths return a value

The isHigherPrecedenceThan routine returns an explicit value for many different combinations of characters, but if none of those conditions match, the routine falls through and does not return a value. It would better to make sure that a value is always returned, as in the following suggestion.

Simplify your code

In the isHigherPrecedenceThan routine, the code only returns true in nine specific cases and false in all other cases. For this reason, we can greatly simplify the code:

bool isHigherPrecedenceThan(char currSymbol, char onStack) {
    return  ((currSymbol == '*' || currSymbol == '/' || currSymbol == '^') 
                && (onStack == '+' || onStack == '-')) 
            || (currSymbol == '^' 
                && (onStack == '*' || onStack == '/' || onStack == '^'));
}

Consider the use of objects

If you had an Operator class, a number of things would be simplified. For example, instead of having the code above as a standalone function, one could implement it as operator> and keep all of operator-specific parts in once place.

Use return values

The main routine defines an empty string and the passes it to the convertToPostfix routine to fill in. I'd expect instead that convertToPostfix would return the string. Also, if you have the C++17 std::optional available, I think I'd prefer that to using exceptions.

Consider better error checking

The current code accepts ;;';'[]^_=!@#$% as a valid infix string. That doesn't seem correct. It may be better to check for only valid characters.

Consider unary vs. binary functions

If we write "-8" it's clear that "-" is being used as a unary function with a single argument "8". If we write "9-8" the "-" is a binary function that has a somewhat different purpose. The current code makes no such distinction and accepts "-a" and renders "a-" which may be acceptable, but it's unlikely that "a^" is currectly translated as "a^".