If you intend to work as a professional programmer in the scientific or financial sectors for any reasonable length of time, then infix evaluation is a problem you’re likely to encounter a lot. After all, programmers aren’t the only people who have to deal with complex mathematical expressions. Whilst the most popular solutions often rely on an intermediate prefix/postfix stage, I have chosen to employ a more direct approach here. In the interests of clarity, I’ll begin with an iterative C++ precedence-based evaluator, and subsequently add parentheses support as a retrofit.
As it’s not always convenient to create an std::exception subclass for every conceivable class of error — the standard C++ exception paradigm is primarily centred around inheritance — we’ll grease the rails a little by deriving a more versatile parameter-based exception class. Maintaining compatibility with the existing ‘throw → catch → what()’ mechanism, this new class facilitates the use of error names, codes, and messages at the point of dissemination (i.e. the point at which the exception is thrown).
The basic mechanics of this class may be summarised as follows:
An exception of type “ApplicationException” is thrown, thus:
The exception is subsequently caught.
The exception object’s “what()” method is used to return an error report of type:
ApplicationException.h
/* =============================================================================
Concrete base class from which all other application-related exceptions should
be derived. As this class is derived from the standard C++ exception class, it
maintains compatibility with the standard "throw -> catch -> what()" mechanism,
whilst facilitating the use of discriminating error names, codes, and messages
at the point of dissemination (i.e. the point at which the exception is thrown).
As this effectively permits each "throw" statement to distinguish itself from
its peers, the number of unique 'std::exception' subclasses should be
drastically reduced.
============================================================================= */
#ifndef APPLICATION_EXCEPTION_ALREADY_INCLUDED
#define APPLICATION_EXCEPTION_ALREADY_INCLUDED
#include <string>
#include <exception>
// Class is a derivation of "std::exception".
class ApplicationException : public std::exception {
private:
// Private member variables to store error code, error message, and error
// name information. As performance is not a consideration here,
// std::string objects are used for all string-related data.
const int mCode;
const std::string mMessage;
const std::string mName;
protected:
// Protected member variable to store the "what()" method's return string.
// Derived classes will require direct access should they wish to augment
// this error string.
std::string mReport;
public:
// Constructor method.
ApplicationException(const int pCode,
const char *pMessage,
const char *pName = "ApplicationException") noexcept;
// Methods to return the error code, error message, and error name
// associated with this object.
int code() const noexcept;
const char* message() const noexcept;
const char* name() const noexcept;
// Overridden std::exception "what()" method.
virtual const char* what() const noexcept override;
};
#endif
// =============================================================================
ApplicationException.cpp
#include "ApplicationException.h"
// =============================================================================
// Constructor method.
// PARAMETERS: 1) Error code associated with this exception.
// 2) Error message associated with this exception.
// 3) Error name (default = "ApplicationException").
ApplicationException::ApplicationException(const int pCode,
const char *pMessage,
const char *pName) noexcept
: // Assign error parameters to this object.
mCode(pCode),
mMessage(pMessage),
mName(pName),
// Generate a report string of type:
// Error_Name
// **********
//
// Error_Code : Error_Message
// Typically, this string is returned via the overridden
// "std::exception::what()" method.
mReport(std::string(mName) + "\n" + std::string(mName.length(), '*') +
"\n\n" + std::to_string(mCode) + " : " + mMessage) {}
// =============================================================================
// Method to return the error code associated with this exception.
int ApplicationException::code() const noexcept {
return mCode;
}
// =============================================================================
// Method to return the error message associated with this exception.
const char* ApplicationException::message() const noexcept {
return mMessage.c_str();
}
// =============================================================================
// Method to return the error name associated with this exception.
const char* ApplicationException::name() const noexcept {
return mName.c_str();
}
// =============================================================================
// Overridden "std::exception::what()" method. Typically, this method returns
// the report string created during object construction.
const char* ApplicationException::what() const noexcept {
return mReport.c_str();
}
// =============================================================================
As it’s often useful to report the position of an error during the evaluation of an infix expression, it makes sense to extend this exception class accordingly. Accommodating both expression and position parameters, the derived class’s “what()” method subsequently returns an error report of type:
NOTE: The above example assumes an error at character position 3 of the supplied expression.
InfixParseException.h
/* =============================================================================
Exception class for all infix-related parsing errors. A derivative of
"ApplicationException", this class additionally facilitates the reporting of
both expression and error position information.
============================================================================= */
#ifndef INFIX_PARSE_EXCEPTION_ALREADY_INCLUDED
#define INFIX_PARSE_EXCEPTION_ALREADY_INCLUDED
#include "ApplicationException.h"
// Class is a derivation of "ApplicationException".
class InfixParseException : public ApplicationException {
private:
// Private member variables to store expression and error position
// information.
const std::string mExpression;
const unsigned int mPosition;
public:
// Constructor method.
InfixParseException(const int pCode,
const char *pMessage,
const char *pExpression,
const unsigned int pPosition);
// Methods to return the expression and error position associated with
// this object.
const char* expression() const noexcept;
int position() const noexcept;
};
#endif
// =============================================================================
InfixParseException.cpp
#include "InfixParseException.h"
// =============================================================================
// Constructor method.
// PARAMETERS: 1) Error code associated with this exception.
// 2) Error message associated with this exception.
// 3) Infix expression associated with this exception.
// 4) Character position at which the exception occured.
InfixParseException::InfixParseException(const int pCode,
const char *pMessage,
const char *pExpression,
const unsigned int pPosition)
: // Initialise parent instance (exception name is implicitly changed to
// "InfixParseException") and assign additional error parameters to this
// object.
ApplicationException(pCode, pMessage, "InfixParseException"),
mExpression(pExpression),
mPosition(pPosition) {
// Augment report string with additional error parameters:
// Expression
// **********
//
// Exp{@Position}ression
mReport += "\n\nExpression\n**********\n\n" +
mExpression.substr(0, mPosition) + "{@" +
std::to_string(mPosition) + "}" +
mExpression.substr(mPosition, mExpression.length() - mPosition);
}
// =============================================================================
// Method to return the expression associated with this exception.
const char* InfixParseException::expression() const noexcept {
return mExpression.c_str();
}
// =============================================================================
// Method to return the error position associated with this exception.
int InfixParseException::position() const noexcept {
return mPosition;
}
// =============================================================================
As we’ve decided to implement an iterative rather than a recursive solution here, we’ll need to employ explicit operand/operator stacks as part of our infix sequencing mechanism. Whilst I’ve never been overly fond of the standard C++ library, writing an entire stack template is somewhat overkill for the demonstration code presented here. Thus, for convenience, we’ll be using the standard std::stack template, albeit with the following modifications:
Its “pop” method shall be modified to conform to canonical stack behaviour: popped values should always be returned to the caller.
For convenience, an explicit method shall be provided that allows us to reset the stack to a previous state (i.e. to delete all but the first n stack elements).
InfixStack.h
/* =============================================================================
A convenience derivative of "std::stack", this modified template effectively
adds both reset functionality and canonical "pop" semantics (i.e. "popped"
values are implicitly returned to the caller).
============================================================================= */
#ifndef INFIX_STACK_ALREADY_INCLUDED
#define INFIX_STACK_ALREADY_INCLUDED
#include <cstddef>
#include <stack>
// Template is a derivation of "std::stack".
template<class T> class InfixStack : public std::stack<T> {
public:
// =======================================================================
// Alternate "pop" method which canonically retuns the popped value.
T pop() {
// Copy element at top of stack.
T v = std::stack<T>::top();
// Remove value from top of stack.
std::stack<T>::pop();
// Return copied element.
return v;
}
// =======================================================================
// Method to reset the stack to an earlier state (i.e. only the first "pN"
// entries are preserved). Note: this method does nothing if the current
// stack size is lessthan or equal to "pN".
// PARAMETERS: 1) Number of entries to preserve (default = 0).
void reset(size_t pN = 0) {
// Iteratively pop elements off the stack, until size <= "pN".
while (std::stack<T>::size() > pN)
std::stack<T>::pop();
}
};
#endif
// =============================================================================
With the ancillary drudge out of the way, we can now concentrate on the evaluator classes themselves. For this, we’ll require the services of two discrete interfaces: one to represent the properties of each operator (i.e. symbol, precedence, associativity, and function), and the other to encapsulate the main evaluator functionality. Due to the intrinsic dependency between these two interfaces -- infix operators infur meaning only within the context of an evaluator -- inner classes appear to offer the greatest degree of generality here. As such, each operator class will be semantically contained within the main evaluator class itself.
When considering the various mechanics and minutiae of the evaluator class as a whole, it’s somewhat useful to acknowledge the following observations:
Operators must always be evaluated in the order dictated by their established precedence and associativity (BODMAS/BEDMAS).
As an operator’s precedence/associativity is inextricably linked to that of its immediate neighbour, the entire expression can be parsed in a single left-to-right sweep (i.e. it’s sufficient to compare each operator with its immediate neighbour, rather than the entire expression).
As neighbours of increasing precedence are always evaluated in a left-to-right fashion, lower-precedence operators must be ‘remembered’ and subsequently recalled in reverse, right-to-left order (i.e. when processing higher-precedence operators from left-to-right, deferred lower-precedence operators naturally occur in an increasing order of precedence). Therefore, LIFO stack structures represent the best fit for this purpose.
Thus, with this in mind, we’ll adopt the following strategy whilst attempting to implement our super-duper no-nonsense XR4i evaluator method (if that doesn’t betray my age, nothing will):
From left to right, if the current operator has higher precedence than the operator currently situated at the top of the operator stack, then push the current operator and the subsequent operand onto their respective stacks, and move on to the next operator. Else, pop the top-most operator and its associated operand(s) from their respective stacks, and push the result of the operation back onto the operand stack.
Repeat step #1 until the entire infix expression has been parsed and the operator stack is empty.
Pop the final result from the top of the operand stack.
There are, of course, a few corner cases that the above procedure conveniently ignores, such as the initial state, empty stack, and end-of-expression conditions. Whilst these are typically handled via additional program code, I’ve opted to incorporate them into the existing precedence logic by biasing the operator stack with ancillary non-arithmetic start and end operators (each denoting the beginning and end of the expression, respectively).
InfixEvaluator.h
/* =============================================================================
Class to encapsulate the functionality of a stack-based iterative infix
expression evaluator. As extensive use is made of object state, rather than
static/stacked state, this class must be instantiated before use. Due to the
exclusive relationship between an evaluator and its operators (operators
intrinsically require an evaluator context), inner operator classes have been
employed where appropriate.
============================================================================= */
#ifndef INFIX_EVALUATOR_ALREADY_INCLUDED
#define INFIX_EVALUATOR_ALREADY_INCLUDED
#include "InfixStack.h"
// Outer evaluator class.
class InfixEvaluator {
// =========================================================================
// Abstract inner operator class from which all other operator classes are
// derived.
class InfixOperator {
private:
// Private member variables to store symbol, precedence, and
// associativeness information.
char mSymbol;
unsigned int mPrecedence;
bool mIsLeftAssociative;
public:
// Constructor method.
InfixOperator(char pSymbol,
unsigned char pPrecedence,
bool pIsLeftAssociative);
// Methods to return the symbol, precedence, and associativeness
// attributed to this object.
char symbol() const;
unsigned int precedence() const;
bool isLeftAssociative() const;
// Pure virtual method used to implement the operator's evaluation
// logic.
virtual void evaluate(InfixEvaluator &pEvaluator) const = 0;
};
// =========================================================================
// Convenience macro used to declare concrete operator classes.
#define OPERATOR_CLASS(NAME) \
class NAME : public InfixOperator { \
public: \
NAME(); \
virtual void evaluate(InfixEvaluator &pEvaluator) const override; }
// Inner concrete operator classes.
OPERATOR_CLASS(StartOperator);
OPERATOR_CLASS(ExponentOperator);
OPERATOR_CLASS(DivideOperator);
OPERATOR_CLASS(ModuloOperator);
OPERATOR_CLASS(MultiplyOperator);
OPERATOR_CLASS(AddOperator);
OPERATOR_CLASS(SubtractOperator);
OPERATOR_CLASS(UnaryMinusOperator);
OPERATOR_CLASS(UnaryPlusOperator);
OPERATOR_CLASS(EndOperator);
// =========================================================================
private:
// Static instance of each operator (operators don't have local state).
static const StartOperator scmStartOperator;
static const ExponentOperator scmExponentOperator;
static const DivideOperator scmDivideOperator;
static const ModuloOperator scmModuloOperator;
static const MultiplyOperator scmMultiplyOperator;
static const AddOperator scmAddOperator;
static const SubtractOperator scmSubtractOperator;
static const UnaryMinusOperator scmUnaryMinusOperator;
static const UnaryPlusOperator scmUnaryPlusOperator;
static const EndOperator scmEndOperator;
// Member variables to store the expression, current expression character,
// and current operator pointers.
const char *mExpression;
const char *mExpressionChar;
const InfixOperator *mCurrentOperator;
// Member variables to store operand and operator stacks.
InfixStack<double> mOperandStack;
InfixStack<const InfixOperator*> mOperatorStack;
// Methods to parse an expected operand/operator at the current expression
// character position (mExpressionChar).
double parseOperand();
const InfixOperator* parseOperator();
public:
// Constructor method.
InfixEvaluator();
// Infix evaluation method.
double evaluate(const char *pExpression);
};
#endif
// =============================================================================
InfixEvaluator.cpp
#include "InfixEvaluator.h"
#include "InfixParseException.h"
#include <cmath>
// =============================================================================
// For convenience, we define the outer class name here; from here on down, the
// outer class name is accessible via the 'OUTER' macro.
#define OUTER InfixEvaluator
// =============================================================================
// Infix operator inner class constructor method.
// PARAMETERS: 1) Operator symbol
// 2) Operator precedence
// 3) Is operator left-associative
OUTER::InfixOperator::InfixOperator(char pSymbol,
unsigned char pPrecedence,
bool pIsLeftAssociative)
: mSymbol(pSymbol),
mPrecedence(pPrecedence),
mIsLeftAssociative(pIsLeftAssociative) {}
// =============================================================================
// Infix operator inner class 'return symbol' method.
// RETURNS: The symbol associated with this operator.
char OUTER::InfixOperator::symbol() const {
return mSymbol;
}
// =============================================================================
// Infix operator inner class 'return precedence' method.
// RETURNS: The precedence value associated with this operator.
unsigned int OUTER::InfixOperator::precedence() const {
return mPrecedence;
}
// =============================================================================
// Infix operator inner class 'return left-associative' method.
// RETURNS: Whether or not this operator is left-associative.
bool OUTER::InfixOperator::isLeftAssociative() const {
return mIsLeftAssociative;
}
// =============================================================================
// Macro to denote the beginning of the infix precedence entries: the
// precedence counter is effectively reset to zero, and constants are defined
// for the number of precedence bits used and its associated overflow value
// (i.e. max precedence + 1).
// MACRO PARAMETERS: 1) Number of bits required to represent precedence values.
#define INFIX_PRECEDENCE_BEGIN(NUMBER_OF_BITS) \
constexpr unsigned int cInitialCounter = __COUNTER__; \
constexpr unsigned int cPrecedenceBits = NUMBER_OF_BITS; \
constexpr unsigned int cPrecedenceOverflow = (1 << cPrecedenceBits)
// Helper macro to return the current precedence value (autoincremented upon
// each invocation). Essentially, this macro returns the autoincremented
// system-wide counter, minus its initial value when the INFIX_PRECEDENCE_BEGIN
// macro was last executed (-1 to ensure it's zero-based).
#define INFIX_COUNTER (__COUNTER__ - cInitialCounter - 1)
// Macro to define consecutive incremental precedence constants (autoincremented
// upon each invocation).
// MACRO PARAMETERS: 1) C++ constant name.
#define INFIX_PRECEDENCE(NAMED_CONSTANT) \
constexpr unsigned int NAMED_CONSTANT = INFIX_COUNTER
// Macro to denote the end of the infix precedence entries: a static assert is
// issued at compile time, if the number of consecutive entires exceeds that
// which is representable by the specified number of precedence bits.
#define INFIX_PRECEDENCE_END \
constexpr unsigned int cFinalCounter = INFIX_COUNTER; \
static_assert(cFinalCounter <= cPrecedenceOverflow, \
"Precedence exceeds number of bits!")
// Define the precedence values used within this application (each consecutive
// entry has a higher value than its predecessor).
INFIX_PRECEDENCE_BEGIN(3);
INFIX_PRECEDENCE(cEndPrecedence);
INFIX_PRECEDENCE(cStartPrecedence);
INFIX_PRECEDENCE(cAddSubPrecedence);
INFIX_PRECEDENCE(cDivModMulPrecedence);
INFIX_PRECEDENCE(cUnaryPrecedence);
INFIX_PRECEDENCE(cExponentPrecedence);
INFIX_PRECEDENCE_END;
// =============================================================================
// Convenience macro for defining a monadic infix operator function (the 'RHS'
// parameter tag may be safely referenced from within the macro's 'EXPRESSION'
// argument).
//
// All monadic functions exhibit the following pattern:
//
// 1) Right-hand side (RHS) operand is popped off the operand stack.
// 2) The value of "operator RHS" is pushed back onto the operand stack.
// MACRO PARAMETERS: 1) Name of the outer InfixEvaluator object pointer.
// 2) C/C++ code that defines the operator's functionality.
#define INFIX_MONAD(EVALUATOR, EXPRESSION) \
double RHS = EVALUATOR.mOperandStack.pop(); \
EVALUATOR.mOperandStack.push(EXPRESSION)
// Convenience macro for defining a dyadic infix operator function (both 'LHS'
// & 'RHS' parameter tags may be safely referenced from within the macro's
// 'EXPRESSION' argument).
//
// All dyadic functions exhibit the following pattern:
//
// 1) Right-hand side (RHS) operand is popped off the operand stack.
// 2) Left-hand side (LHS) operand is popped off the operand stack.
// 3) The value of "LHS operator RHS" is pushed back onto the operand stack.
// MACRO PARAMETERS: 1) Name of the outer InfixEvaluator object pointer.
// 2) C/C++ code that defines the operator's functionality.
#define INFIX_DYAD(EVALUATOR, EXPRESSION) \
double RHS = EVALUATOR.mOperandStack.pop(); \
double LHS = EVALUATOR.mOperandStack.pop(); \
EVALUATOR.mOperandStack.push(EXPRESSION)
// =============================================================================
// Convenience macro for defining the implementation of a concrete operator
// class. This implementation consists of a constructor and an overridden
// 'evluate' method.
// MACRO PARAMETERS: 1) Name of the operator class.
// 2) Character symbol associated with this operator.
// 3) Precedence value associated with this operator.
// 4) Is operator left-associative (bool).
// 5) C/C++ code that defines the operator's functionality.
// For convenience, the DYAD or MONAD macros are typically
// employed here.
#define OPERATOR_IMPLEMENTATION(NAME, SYMBOL, PRECEDENCE, LEFT_ASSOCIATIVE, \
EXPRESSION) \
\
/* Concrete operator inner class constructor method. */ \
OUTER::NAME::NAME() \
: InfixOperator(SYMBOL, PRECEDENCE, LEFT_ASSOCIATIVE) {} \
\
/* Concrete operator inner class 'evaluate' method. */ \
\
/* PARAMETERS: 1) Reference to outer evaluator object. For maximum */ \
/* generality, all processing will be performed within the */ \
/* context of the outer object. This parameter can be */ \
/* safely referenced by name via the macro's 'EXPRESSION' */ \
/* parameter. */ \
void OUTER::NAME::evaluate(OUTER &pEvaluator) const {EXPRESSION}
// Define implementation for concrete 'StartOperator' class.
OPERATOR_IMPLEMENTATION(StartOperator, '[', cStartPrecedence, false,)
// Define implementation for concrete 'ExponentOperator' class.
OPERATOR_IMPLEMENTATION(ExponentOperator, '^', cExponentPrecedence, false,
INFIX_DYAD(pEvaluator, pow(LHS, RHS));)
// Define implementation for concrete 'DivideOperator' class. An exception is
// thrown if the RHS operand is zero.
OPERATOR_IMPLEMENTATION(DivideOperator, '/', cDivModMulPrecedence, true,
if (!pEvaluator.mOperandStack.top())
throw ApplicationException(-3, "Division by zero");
INFIX_DYAD(pEvaluator, LHS / RHS);)
// Define implementation for concrete 'ModuloOperator' class. An exception is
// thrown if the RHS operand is zero.
OPERATOR_IMPLEMENTATION(ModuloOperator, '%', cDivModMulPrecedence, true,
if (!pEvaluator.mOperandStack.top())
throw ApplicationException(-4, "Modulo of zero");
INFIX_DYAD(pEvaluator, fmod(LHS, RHS));)
// Define implementation for concrete 'MultiplyOperator' class.
OPERATOR_IMPLEMENTATION(MultiplyOperator, '*', cDivModMulPrecedence, true,
INFIX_DYAD(pEvaluator, LHS * RHS);)
// Define implementation for concrete 'AddOperator' class.
OPERATOR_IMPLEMENTATION(AddOperator, '+', cAddSubPrecedence, true,
INFIX_DYAD(pEvaluator, LHS + RHS);)
// Define implementation for concrete 'SubtractOperator' class.
OPERATOR_IMPLEMENTATION(SubtractOperator, '-', cAddSubPrecedence, true,
INFIX_DYAD(pEvaluator, LHS - RHS);)
// Define implementation for concrete 'UnaryMinusOperator' class.
OPERATOR_IMPLEMENTATION(UnaryMinusOperator, '-', cUnaryPrecedence, false,
INFIX_MONAD(pEvaluator, -RHS);)
// Define implementation for concrete 'UnaryPlusOperator' class.
OPERATOR_IMPLEMENTATION(UnaryPlusOperator, '+', cUnaryPrecedence, false,
INFIX_MONAD(pEvaluator, RHS);)
// Define implementation for concrete 'EndOperator' class.
OPERATOR_IMPLEMENTATION(EndOperator, '[', cEndPrecedence, false,)
// =============================================================================
// Declare storage for outer InfixEvaluator static operator objects.
const OUTER::StartOperator OUTER::scmStartOperator;
const OUTER::ExponentOperator OUTER::scmExponentOperator;
const OUTER::DivideOperator OUTER::scmDivideOperator;
const OUTER::ModuloOperator OUTER::scmModuloOperator;
const OUTER::MultiplyOperator OUTER::scmMultiplyOperator;
const OUTER::AddOperator OUTER::scmAddOperator;
const OUTER::SubtractOperator OUTER::scmSubtractOperator;
const OUTER::UnaryMinusOperator OUTER::scmUnaryMinusOperator;
const OUTER::UnaryPlusOperator OUTER::scmUnaryPlusOperator;
const OUTER::EndOperator OUTER::scmEndOperator;
// =============================================================================
// Outer InfixEvaluator method to parse an expected operand at the current
// expression position, referenced via the 'mExpressionChar' member variable.
// Leading unary operators are iteratively stacked, and an 'InfixParseException'
// exception is thrown in the event of an absent or invalid operand.
// RETURNS: The next infixed operand.
double OUTER::parseOperand() {
do {
// Test current expression character.
switch(*mExpressionChar++) {
// Do nothing if current expression character is space or tab (i.e. skip
// past white space).
case ' ':
case '\t':
break;
// Push unary minus operator onto operator stack if current expression
// character is '-'.
case '-':
mOperatorStack.push(&scmUnaryMinusOperator);
break;
// Push unary plus operator onto operator stack if current expression
// character is '+'.
case '+':
mOperatorStack.push(&scmUnaryPlusOperator);
break;
// Else, parse and return numeric operand, or throw exception upon error.
default:
char *endptr;
double operand = strtod(--mExpressionChar, &endptr);
if (endptr == mExpressionChar)
throw InfixParseException(-1, "Operand expected", mExpression,
mExpressionChar - mExpression);
mExpressionChar = endptr;
return operand;
}
// Test next exception character.
} while (true);
}
// =============================================================================
// Outer InfixEvaluator method to parse an expected operator at the current
// expression position, referenced via the 'mExpressionChar' member variable. An
// 'InfixParseException' exception is thrown in the event of an absent or
// invalid operator.
// RETURNS: The next infixed operator.
const OUTER::InfixOperator* OUTER::parseOperator() {
// Skip past any whitespace characters at the current expression position.
while ((' ' == *mExpressionChar) || ('\t' == *mExpressionChar))
mExpressionChar++;
// Test the current expression character and return the appropriate operator
// object, or throw exception upon error.
switch (*mExpressionChar++) {
// Return exponent operator.
case '^':
return &scmExponentOperator;
// Return division operator.
case '/':
return &scmDivideOperator;
// Return modulo operator.
case '%':
return &scmModuloOperator;
// Return multiplication operator.
case '*':
return &scmMultiplyOperator;
// Return addition operator.
case '+':
return &scmAddOperator;
// Return subtraction operator.
case '-':
return &scmSubtractOperator;
// Return end of expression operator.
case '\0':
return &scmEndOperator;
// Character is not a valid operator, so throw exception.
default:
throw InfixParseException(-2, "Operator or EOL expected", mExpression,
mExpressionChar - mExpression - 1);
}
}
// =============================================================================
// Outer InfixEvaluator constructor method.
OUTER::OUTER() {
// Initialise the bottom of the operator stack with a permanent instance of
// 'scmStartOperator'. This will remain in situ for the life of the object,
// simplifying the conditional logic of the main evaluation loop.
mOperatorStack.push(&scmStartOperator);
}
// =============================================================================
// Outer InfixEvaluator evaluation method.
// PARAMETERS: 1) Infix expression to be evaluated.
// RETURNS...: The evaluated valued of the supplied infix expression.
double OUTER::evaluate(const char *pExpression) {
try {
// Initialise object's expression and expression character pointers.
mExpression = mExpressionChar = pExpression;
// For simplicity, we'll initialise the current operator to
// 'scmStartOperator'. As this operator is right-associative, it's
// implicitly pushed onto the operator stack during the first iteration, and
// harmlessly popped off again during the last (this operator performs a
// NOP).
mCurrentOperator = &scmStartOperator;
do {
// If the operator at the top of the operator stack has higher precedence
// than the current operator, or has the same precedence and is left-
// associative, then pop and evaluate its value. Else, push the current
// operator and next operand onto their respective stacks, and move onto
// the next operator within the expression.
if ((mCurrentOperator->precedence() -
mOperatorStack.top()->isLeftAssociative() -
mOperatorStack.top()->precedence()) >> cPrecedenceBits) {
mOperatorStack.pop()->evaluate(*this);
} else {
mOperatorStack.push(mCurrentOperator);
mOperandStack.push(parseOperand());
mCurrentOperator = parseOperator();
}
// Continue the evaluation until the implicitly pushed 'scmStartOperator'
// is eventually popped off the operator stack. NOTE: the permanent
// 'scmStartOperator' placed on the operator stack during object
// construction, remains in situ for the next evaluation (i.e. the
// operator stack size is always > 0).
} while (mOperatorStack.size() > 1);
// Pop and return the final entry from the operand stack.
return mOperandStack.pop();
// In the event of an exception, we must ensure that both operand and
// operator stacks are reset to their initialised state.
} catch (std::exception &pException) {
// Remove all elements from the operand stack.
mOperandStack.reset();
// Remove all but the permanent 'scmStartOperator' from the operator stack.
mOperatorStack.reset(1);
// Rethrow the caught exception.
throw;
}
}
// =============================================================================
Glancing through the code above, there are a couple of interesting points to note about this particular implementation:
In an effort to significantly reduce code repetition (and thus protect my sanity), C macros have been used liberally throughout. Sorry guys, but ‘Macrophobia’ is merely the illogical fear of an otherwise useful, and IMHO, irreplaceable tool.
As previously mentioned, all operators are implemented via inner classes encapsulated within the evaluator class itself. For maximum flexibility, the operator’s ‘evaluate’ method receives a reference to the outer evaluator object rather than the operands themselves (as is usually the case).
Appropriately biased “StartOperator” and “EndOperator” operators are employed to ‘mainstream’ the corner-case logic (i.e. the initial state, empty stack, and end-of-expression conditions are all handled by the existing precedence logic). Of particular interest, a permanent “StartOperator” object should ALWAYS be present at the bottom of the operator stack: special care should be taken to restore this state in the event of an evaluation exception. Due to the minimal initialisation state, it should also be noted that a second “StartOperator” is innocuously pushed and popped at the beginning and end of the evaluation process, respectively.
The primary precedence/associativity condition used within this code is merely the arithmetic equivalent of the standard precedence & associativity conditions:
Having a working implementation is all well and good, but an infix expression is of little value if we cannot use parentheses to override the default precedence. Thankfully, given the generalised approach adopted thus far, it’s a relatively trivial task to implement parentheses support within the existing class structure.
First, we’ll need to define two new operator classes for the left and right parentheses, respectively:
OPERATOR_CLASS(LeftParenthesisOperator);
OPERATOR_CLASS(RightParenthesisOperator);
...
static const LeftParenthesisOperator scmLeftParenthesisOperator;
static const RightParenthesisOperator scmRightParenthesisOperator;
… and define their precedence and implementation:
INFIX_PRECEDENCE_BEGIN();
INFIX_PRECEDENCE(cEndPrecedence);
INFIX_PRECEDENCE(cRightParenthesisPrecedence);
INFIX_PRECEDENCE(cLeftParenthesisPrecedence);
INFIX_PRECEDENCE(cStartPrecedence);
INFIX_PRECEDENCE(cAddSubPrecedence);
INFIX_PRECEDENCE(cDivModMulPrecedence);
INFIX_PRECEDENCE(cUnaryPrecedence);
INFIX_PRECEDENCE(cExponentPrecedence);
...
// Define implementation for concrete 'LeftParenthesisOperator' class.
OPERATOR_IMPLEMENTATION
(LeftParenthesisOperator, '(', cLeftParenthesisPrecedence, true,
if (pEvaluator.mCurrentOperator != &pEvaluator.scmRightParenthesisOperator)
throw InfixParseException(-5, "Right parenthesis expected",
pEvaluator.mExpression,
pEvaluator.mExpressionChar -
pEvaluator.mExpression - 1);
pEvaluator.mCurrentOperator = pEvaluator.parseOperator();)
...
// Define implementation for concrete 'RightParenthesisOperator' class.
OPERATOR_IMPLEMENTATION(RightParenthesisOperator, '(',
cRightParenthesisPrecedence, false,)
The left parenthesis operator, having checked the current operator is a right parenthesis (only a right parenthesis or an end operator has the precedence to force its evaluation), merely parses the next operator from the expression string. The right parenthesis operator, which is never evaluated, performs a no-operation (NOP).
Next, we’ll need to declare storage for our two new operators and update the operand and operator parsing methods to return each of them, respectively:
const OUTER::LeftParenthesisOperator OUTER::scmLeftParenthesisOperator;
const OUTER::RightParenthesisOperator OUTER::scmRightParenthesisOperator;
...
// Push left parenthesis operator onto operator stack if current
// expression character is '('.
case '(':
mOperatorStack.push(&scmLeftParenthesisOperator);
break;
...
// Return right parenthesis operator.
case ')':
return &scmRightParenthesisOperator;
Finally, the Start operator’s ‘evaluate’ method should be updated to check for any unmatched right parentheses (an unmatched right parenthesis will drive the evaluation back to the nearest start operator):
// Define implementation for concrete 'StartOperator' class.
OPERATOR_IMPLEMENTATION(StartOperator, '[', cStartPrecedence, false,
if (pEvaluator.mCurrentOperator != &pEvaluator.scmEndOperator)
throw InfixParseException(-6, "Unmatched right parenthesis",
pEvaluator.mExpression,
pEvaluator.mExpressionChar -
pEvaluator.mExpression - 1);)
In the interests of completeness, we’ll also include an example ‘main.cpp’ and basic Makefile for good measure:
main.cpp
#include <iostream>
#include "InfixEvaluator.h"
#include "ApplicationException.h"
int main(int argc, char *argv[]) {
int returnCode;
try {
std::cout << "\n"
"=========================\n"
"Iterative Infix Evaluator\n"
"(C) 2025, The Code Asylum\n"
"=========================\n\n";
if (argc != 2) {
std::cout << "Usage: InfixEvaluator 'expression'";
} else {
InfixEvaluator ie;
double answer = ie.evaluate(argv[1]);
std::cout << argv[1] << " = " << answer;
}
returnCode = 0;
} catch (const ApplicationException &pException) {
std::cout << pException.what();
returnCode = pException.code();
} catch (const std::exception &pException) {
std::cout << pException.what();
returnCode = -1;
}
std::cout << "\n\n";
return returnCode;
}
Makefile
CC = g++
LD = g++
EXEC = InfixEvaluator
LFLAGS =
CFLAGS = -O2 -DNDEBUG
################################################################################
$(EXEC): main.o \
ApplicationException.o \
InfixParseException.o \
InfixEvaluator.o
$(LD) $^ -o $@ $(LFLAGS)
main.o: main.cpp
$(CC) $(CFLAGS) -c $< -o $@
ApplicationException.o: ApplicationException.cpp ApplicationException.h
$(CC) $(CFLAGS) -c $< -o $@
InfixParseException.o: InfixParseException.cpp InfixParseException.h
$(CC) $(CFLAGS) -c $< -o $@
InfixEvaluator.o: InfixEvaluator.cpp InfixEvaluator.h
$(CC) $(CFLAGS) -c $< -o $@
################################################################################
all: $(EXEC)
################################################################################
clean:
@rm -rf $(EXEC)
@rm -rf *.o
################################################################################
For those wishing to follow along, the video below presents a visualisation of this particular algorithm at work:
All of the code related to this article is available at our git repository.
In part 2, we’ll take a look at how a recursive solution achieves the same result without explicit std::stack structures.
Top comments (0)