This is a simple excerise in writing an expression parser and evaluator. We will begin with writing the simpliest kind of evaluator and then add on more complex behaviour. Finally, we will build an AST from the expression.
The easiest way to parse and evaluate any expression is to read it left to right and apply each operator as we encounter them.
1+2*3 = 9
Of course, this will give us the wrong answer, but it's a start. Let's begin.
This is our main():
#include <iostream>int main(int argc, char * argv[]){if(!argv[1]){std::cout << "You must invoke this program with an expression\n";return 1;}char const * text = argv[1];int result;if(eval(text, result)){std::cout << result << std::endl;}else{std::cout << "There seems to be an error here: '" << text << "'\n";return 1;}return 0;}
The program
expects one argument, the expression to evaluate. We call eval() with
a pointer to this expression. If an error occurs, the pointer will point to
the offending character. Otherwise, it prints the result.
Next up is eval():
bool eval(char const *& pos, int & result){if(!pos){return false;}return read_expression(pos, result) && !*pos;}
It doesn't do much. We do make sure that pos isn't a null pointer.
The !*pos condition makes sure to only return true if the entire
expression has been parsed.
The read_expression() function is as follows:
bool read_expression(char const *& pos, int & result){if(read_number(pos, result)){Operator op;while(read_operator(pos, op)){int num;if(!read_number(pos, num)){return false;}if(!compute_binary(op, result, num, result)){return false;}}return true;}return false;}
For an expression to be valid it needs to include at least one number. After
we have read the first one we loop reading an operator and another number.
The calculation is done by compute_binary().
bool read_number(char const *& pos, int & num){num = 0;if(std::isdigit(*pos)){do{num *= 10;num += *pos - '0';++pos;} while(std::isdigit(*pos));return true;}return false;}
read_number() should be pretty easy to understand. We loop and tally up
all the digits into an integer and return it in num. Worth noting is that
we only read positive numbers. We'll return to negative numbers later.
Hint: -2²
enum class Operator{Addition,Subtraction,Multiplication,Division,};bool read_operator(char const *& pos, Operator & op){switch(*pos){case '+':op = Operator::Addition;break;case '-':op = Operator::Subtraction;break;case '*':op = Operator::Multiplication;break;case '/':op = Operator::Division;break;default:return false;}++pos;return true;}
read_operator() will parse an operator and return its enumeration value in op.
We'll start with the four basic math operators +, -, * and /.
We limit ourselves to single byte operators. This will exclude multi byte
unicode operators, for example ×, and operators like ABS. They are easily
added if needed.
Lastly we have compute_binary() which calculates the infix operators.
bool compute_binary(Operator op, int lhs, int rhs, int & result){switch(op){case Operator::Addition:result = lhs + rhs;break;case Operator::Subtraction:result = lhs - rhs;break;case Operator::Multiplication:result = lhs * rhs;break;case Operator::Division:result = lhs / rhs;break;default:return false;}return true;}
We switch on the operator and perform the calculation. Nothing fancy here.
Our first evaluator is now working.
~$ ./a.out 5~$ 5
~$ ./a.out 1+1~$ 2
~$ ./a.out 1-9*2~$ -16
~$ ./a.out 11-9/2~$ 1
Just like we learned in school that multiplication should be done before addition, we need to teach the evaluator that too. This is called operator precedence.
Before we tackle operator precedence we can force multiplication to be calculated before addition if we implement support for parentheses.
1+8
The number 8 can be expressed as 4*2.
1+(4*2)
The number 4 can be expressed as 20/5.
1+((20/5)*2)
The expression inside a pair of parentheses is always just a value to the
outside viewer. This means the best place to parse parentheses is
in read_number(). When read_number() encounters an
opening parenthesis we call read_expression() to get the value.
bool read_number(char const *& pos, int & num){if(*pos == '('){++pos;if(!read_expression(pos, num) || *pos != ')'){return false;}++pos;return true;}num = 0;if(is_digit(*pos)){do{num *= 10;num += *pos - '0';++pos;} while(is_digit(*pos));return true;}return false;}
We can now use parentheses to get the correct answer.
~$ ./a.out 1-9*2~$ -16
~$ ./a.out 1-(9*2)~$ -17
~$ ./a.out (1-((9*(2))))~$ -17
Operator precedence is a way to specify in which order operators are calculated. Operators with a higher precedence are calculated before operators with a lower precedence. When we evaluate the expression,
1+2*3*4+5
we evaluate it from left to right, one operator at a time, but the idea is to complete the multiplication before the addition.
The evaluator will use the p() function to get the precedence level of an
operator. We reserve the precedence level 0, more on that later.
int p(Operator op){switch(op){case Operator::Addition:case Operator::Subtraction:return 10;case Operator::Multiplication:case Operator::Division:return 20;default:return 0;}}
Higher precedence operators take priority over lower ones. Multiplication and division should be done before addition and subraction in an expression.
So how do we actually do it? Remember, we are still reading the expression from left to right. Whenever we parse an operator we need compare it with next operator and see which one has the highest precedence. For example:
1+2*3
When we parse + we can't apply it to 1+2 straight away as we have done
so far. We need to compare p(+) with p(*) and determine that the multiplication
2*3 should be calculated first.
An important part is that everything following an operator is its own expression. The above example can be viewed as:
1+(2*(3))
This is a huge sign of recursion. Instead of parsing the righ hand side
number in read_expression() by calling read_number() we instead recurse.
We exchange read_number() with read_expression().
bool read_expression(char const *& pos, int & result){if(read_number(pos, result)){Operator op;while(read_operator(pos, op)){int num;if(!read_number(pos, num))if(!read_expression(pos, num)){return false;}if(!compute_binary(op, result, num, result)){return false;}}return true;}return false;}
read_expression() recurses into each sub expression. But it
will unfortunately calculate all expressions backwards, as is:
1+2*3+4
will be parsed as:
1+(2*(3+(4)))
So the question becomes, when does a sub expression's operator take precedence over the previous operator? Consider a more generic version:
1 A (2 B 3)
Looking at the relationship between any two operators, there are three kinds of relationships to consider:
p(B) > p(A)
p(B) = p(A)
p(B) < p(A)
In case 1) where B has the higher precedence we should compute 2 B 3 first.
In case 3) where A has the higher precedence we should compute 1 A 2 first.
And lastly, in case 2) when they have the same precedence we will
calculate A before B. This makes the most sense. Consider:
1 + 2 + 3 + 4
which should be calculated as:
(((1 + 2) + 3) + 4)
And:
1 - 2 - 3 - 4
which should be calculated as
(((1 - 2) - 3) - 4)
for it to give the right answer.
This means that case 2) will benefit A just as in case 3).
We can therefore reduce it two just two kinds of relationships:
p(B) > p(A) ➜ B
p(B) <= p(A) ➜ A
B is the current operator and A is the previous.
We can generalize the cases as:
p(current) > p(previous) ➜ current
p(current) <= p(previous) ➜ previous
This means if p(B) <= p(A) is true we should stop parsing the sub expression
and return the result we have.
Case 2) is the only interesting one since it's our condition to stop recursing.
But what about when A is the current operator? What is the previous operator then?
This is where our
reserved zero precedence comes in to play. We introduce the Null operator:
enum class Operator{Null,Addition,Subtraction,Multiplication,Division,};
The Null operator is not a real operator, but it's a virtual operator
so we have something to compare A with.
All operators take precedence before it. We don't even have to change p()
to get the lowest precedence for the Null operator.
We make the changes to read_expression().
It needs an additional parameter, the previous operator.
After reading an operator it needs to check if case 2) is
true or false. If the condition is true we return. Also important is to
put back the operator since we haven't computed it yet.
bool read_expression(char const *& pos, int & result)bool read_expression(char const *& pos, int & result, Operator previous_op){if(read_number(pos, result)){Operator op;while(read_operator(pos, op)){/** Precedence check.*/bool const op_lesseq_previous = p(op) <= p(previous_op);if(op_lesseq_previous){--pos;/** This will break to the `return true` statement.*/break;}int num;if(!read_expression(pos, num, op)){return false;}if(!compute_binary(op, result, num, result)){return false;}}return true;}return false;}
Note that when we recurse into read_expression() we supply it with the
current operator for comparison.
For simplicity we let read_expression() default the previous_op parameter to
Operator::Null.
bool read_expression(char const *& pos, int & result, Operator previous_op = Operator::Null){...}
Suddenly we have proper operator precedence parsing. An expression like,
1-3-2*4*2+3
will now be calculated as,
1-(3)-(2*(4)*(2))+(3)
which is correct.
~$ ./a.out 1-3-2*4*2+3~$ -15
Next we're going to introduce a new operator, the power ^ operator. In the
expression A^B the power operator says that A is raised to the power of B.
Its precedence will be higher than the rest to make sure it is calculated first.
We add it to Operator, read_operator(), p() and compute_binary():
enum class Operator{Null,Addition,Subtraction,Multiplication,Division,Power,};bool read_operator(char const *& pos, Operator & op){switch(*pos){case '+':op = Operator::Addition;break;case '-':op = Operator::Subtraction;break;case '*':op = Operator::Multiplication;break;case '/':op = Operator::Division;break;case '^':op = Operator::Power;break;default:return false;}++pos;return true;}int p(Operator op){switch(op){case Operator::Addition:case Operator::Subtraction:return 10;case Operator::Multiplication:case Operator::Division:return 20;case Operator::Power:return 30;default:return 0;}}bool compute_binary(Operator op, int lhs, int rhs, int & result){switch(op){case Operator::Addition:result = lhs + rhs;break;case Operator::Subtraction:result = lhs - rhs;break;case Operator::Multiplication:result = lhs * rhs;break;case Operator::Division:result = lhs / rhs;break;case Operator::Power:result = std::pow(lhs, rhs);break;default:return false;}return true;}
A simple addition. Let's try it out.
~$ ./a.out 2^4~$ 16
Looks right.
~$ ./a.out 2^2^0~$ 1
That looks wrong, and it is wrong mathematically. Our evaluator does
what we have told it. When the current and the previous operator have the
the same precedence we yield to the previous one. The right answer is
however 2. Exponents are calculated from the highest to the lowest.
The expression should be calculated as 2^(2^0).
How do we solve this? We need some way of make the ^ operator group to the
right like 2^(2^0) instead of (2^2)^0. Enter associativity!
There are two types of associativity, left and right. They determine how the same operator groups when chained.
Left associative operators will group to the left, (this is the default)
a op b op c = ((a op b) op c)
And right associative operators will group to the right
a op b op c = (a op (b op c))
Operator precedence is about determining the order of evaluation between
different operators. Some operators have the same precedence,
like + and -, but they all look the same when determining precedence.
Associativity is about in which order the same operators are evaluated when chained in an expression. Subtraction is done left to right, the expression:
1-2-3
is grouped like:
(1-2)-3
Our ^ operator on the other hand wants to be right associative and
group like:
2^(2^(2^0))
The usual way to specify associativity among operators is to make a precedence level either left or right. There shouldn't be two operators with the same precedence level and different associativity. That is a conflict. Our operator table looks like this:
30 ^ right20 * / left10 + - left
We introduce the a() function which given an operator return its
associativity,
enum class Associativity{Left,Right,};Associativity a(Operator op){switch(op){case Operator::Power:return Associativity::Right;default:return Associativity::Left;}}
The default being left associativity.
Our precedence test in read_expression() needs to be modified. It currently
returns if p(op) <= p(previous_op) but if they have the same precedence
level we need to check associativity. If a(op) is Left we return as previously,
since that is the default behaviour, but if a(op) is Right we should continue
just as if op had higher precedence.
bool read_expression(char const *& pos, int & result, Operator previous_op){if(read_number(pos, result)){Operator op;while(read_operator(pos, op)){/** Precedence check.*/bool const op_lesseq_previous = p(op) <= p(previous_op);if(op_lesseq_previous)bool const op_less_previous = p(op) < p(previous_op);if(op_less_previous){--pos;/** This will break to the `return true` statement.*/break;}/** Associativity check.*/bool const op_equal_previous = p(op) == p(previous_op);bool const op_left_associativity = a(op) == Associativity::Left;if(op_equal_previous && op_left_associativity){--pos;break;}int num;if(!read_expression(pos, num, op)){return false;}if(!compute_binary(op, result, num, result)){return false;}}return true;}return false;}
Our power ^ operator will now function as intended.
~$ ./a.out 2^2^0~$ 2
What we lack now are prefix and suffix operators. These are commonly found
in programming languages so we'll add them too. Affix operators don't really
have any associativity, since associativity involves infix operators. But they
act like they do in some sense. Imagine a prefix operator P and a suffix
operator S. The P operator will group like:
PPP3 = P(P(P3))
and the suffix operator:
3SSS = ((3S)S)S
So we could say that P groups right and S groups left, but that is just
how they are calculated; closest first. And what about this one?
P3S
It depends on the precedence of the operators!
Affix operators are usually called non-associative operators.
As you may have noticed during all of this, and as hinted about way earlier, we
don't have a way to explicitly write negative numbers. The expression -1 will fail.
Instead we need to write 0-1. Why don't we just parse the sign in
read_number()? That way we could write -1 and it would work.
But what about -2^2? It turns out that the sign is actually a prefix operator.
-2^2 should be calculated as -(2^2).
We add the - prefix operator and also the + prefix operator.
enum class Operator{Null,Addition,Subtraction,Multiplication,Division,Power,Negative,Positive,};
All prefix operators have precedence.
The + and - prefix operators have a lower precedence than ^, but
higher than the other operators. +-2*3 should evaluate as (+-2)*3.
So we place them in the middle in p().
int p(Operator op){switch(op){case Operator::Addition:case Operator::Subtraction:return 10;case Operator::Multiplication:case Operator::Division:return 20;case Operator::Negative:case Operator::Positive:return 25;case Operator::Power:return 30;default:return 0;}}
We'll also introduce a new function read_prefix_operator() for parsing.
bool read_prefix_operator(char const *& pos, Operator & op){switch(*pos){case '-':op = Operator::Negative;break;case '+':op = Operator::Positive;break;default:return false;}++pos;return true;}
And we need a function to calculate affix operators.
bool compute_unary(Operator op, int arg, int & result){switch(op){case Operator::Negative:result = arg * -1;break;case Operator::Positive:/** Yes, this is unnecessary.*/result = arg * 1;break;default:return false;}return true;}
But where do we parse prefix operators? Prefix operators only concern
themselves with numbers. If we encounter a prefix when parsing a number
in parse_number()
we call read_expression() to get the number. That way the prefix also
comes into play with its precedence. And through read_expression() we
end up back in read_number() which enables stacking of prefix
operators.
bool read_number(char const *& pos, int & num){if(*pos == '('){++pos;if(!read_expression(pos, num) || *pos != ')'){return false;}++pos;return true;}Operator op;if(read_prefix_operator(pos, op)){if(!read_expression(pos, num, op)){return false;}if(!compute_unary(op, num, num)){return false;}return true;}num = 0;if(is_digit(*pos)){do{num *= 10;num += *pos - '0';++pos;} while(is_digit(*pos));return true;}return false;}
Prefix operators are now fully operational.
-2^2*2
will be parsed as:
(-(2^2))*2
~$ ./a.out -2*-2~$ 4
which is correct.
--+1
will be parsed as:
-(-(+1))
which is also correct.
The last thing we are going to add are suffix operators. We are going to add
the suffix operator ! which is the factorial operator.
enum class Operator{Null,Addition,Subtraction,Multiplication,Division,Power,Positive,Negative,Factorial,};bool read_operator(char const *& pos, Operator & op){switch(*pos){case '+':op = Operator::Addition;break;case '-':op = Operator::Subtraction;break;case '*':op = Operator::Multiplication;break;case '/':op = Operator::Division;break;case '^':op = Operator::Power;break;case '!':op = Operator::Factorial;break;default:return false;}++pos;return true;}
We give it the second highest precedence. We still want exponents
to be calculated before applying the factorial as in 2^2!.
int p(Operator op){switch(op){case Operator::Addition:case Operator::Subtraction:return 10;case Operator::Multiplication:case Operator::Division:return 20;case Operator::Negative:case Operator::Positive:return 25;case Operator::Factorial:return 27;case Operator::Power:return 30;default:return 0;}}
Just like prefix operators, precedence also concern suffix operators.
Any operator after a number could be a suffix operator. Therefore the right place
to evaluate suffixes is after we have checked for precedence in
read_expression() but before we check associativity since suffixes don't
have any.
We need to decide whether the operator is an infix or a suffix operator.
To do so we with the function is_suffix_operator().
bool is_suffix_operator(Operator op){switch(op){case Operator::Factorial:return true;}return false;}
If the operator is a suffix we calculate it. We then continue with the
next operator by issuing a continue.
bool read_expression(char const *& pos, int & result, Operator previous_op){if(read_number(pos, result)){Operator op;while(read_operator(pos, op)){/** Precedence check.*/bool const op_less_previous = p(op) < p(previous_op);if(op_less_previous){--pos;/** This will break to the `return true` statement.*/break;}/** Suffix*/if(is_suffix_operator(op)){if(!compute_unary(op, result, result)){return false;}continue;}/** Associativity check.*/bool const op_equal_previous = p(op) == p(previous_op);bool const op_left_associativity = a(op) == Associativity::Left;if(op_equal_previous && op_left_associativity){--pos;break;}int num;if(!read_expression(pos, num, op)){return false;}if(!compute_binary(op, result, num, result)){return false;}}return true;}return false;}
The only thing remaining is to add the factorial operator to compute_unary(),
bool compute_unary(Operator op, int arg, int & result){switch(op){case Operator::Negative:result = arg * -1;break;case Operator::Positive:result = arg * 1;break;case Operator::Factorial:if(arg < 0){return false;}result = 1;for( ; arg > 1; --arg){result *= arg;}break;default:return false;}return true;}
Our evaluator now supports operator precedence and associativity, as well as affix operators.
~$ ./a.out 3!~$ 6
~$ ./a.out -3!*2+1~$ -11
Instead of evaluating the expression directly, we can build an AST tree representation of the expression instead.
Our AST will be a layer above the functionality already built. We are going to change a few things to make it all work, but it will be minimal.
We want a base class to be the public interface for the AST.
class AST{public:virtual int eval() const noexcept = 0;virtual ~AST() noexcept = default;};
The AST class has only one method eval() which we will use to evaluate
the whole abstracted expression.
The most basic components of any expression are the numbers. They are terminal
and represent the most tangeable part of the expression. All numbers will be
represented by the ASTNumber class.
class ASTNumber : public AST{private:int d_number;public:ASTNumber(int number) : d_number(number){}int eval() const noexcept override{return d_number;}};
The eval() method simply returns the number.
And then we have all the operators actually performing the calculations. There
are two types of operators, infix and affix, or with different names, binary
and unary. Since we are going to leverage the existing framework and use
compute_binary() and compute_unary(), we need to save the Operator object.
The base class for ASTBinary and ASTUnary will be the ASTOperator class.
This might seem like a needless separation of concern by some though.
class ASTOperator : public AST{private:Operator const d_operator;public:ASTOperator(Operator op) : d_operator(op){}Operator get_op() const noexcept{return d_operator;}};
class ASTBinary : public ASTOperator{private:AST * d_lhs = nullptr;AST * d_rhs = nullptr;public:ASTBinary(Operator op, AST * lhs, AST * rhs) : ASTOperator(op), d_lhs(lhs), d_rhs(rhs){}int eval() const noexcept override{int result;if(!compute_binary(get_op(), d_lhs->eval(), d_rhs->eval(), result)){std::abort();}return result;}};
ASTBinary is the work horse for the infix operators. It needs the AST nodes
for the left and right sides. When we call compute_binary() we evaluate both
sides, d_lhs and d_rhs, to get the values. We then return the result.
class ASTUnary : public ASTOperator{private:AST * d_arg = nullptr;public:ASTUnary(Operator op, AST * arg) : ASTOperator(op), d_arg(arg){}int eval() const noexcept override{int result;if(!compute_unary(d_operator, d_arg->eval(), result)){std::abort();}return result;}};
ASTUnary is pretty similar to ASTBinary. Since all affix operators only
operate on one number the constructor only expects one AST node for its
argument.
Both ASTBinary and ASTUnary will call abort() if the calculations fail.
These classes will form our AST tree. Of course if we need more specific
functionality or interactions with the specific operators we could subtype
a new class from either ASTBinary or ASTUnary for them. For example:
class ASTAddition : public ASTBinary{public:ASTAddition(AST * lhs, AST * rhs): ASTBinary(Operator::Addition, lhs, rhs){}};
In our previous incarnations of the evaluator the result parameter was
always an integer. Now when we want to build the abstraction, we need to change
its type to AST*. We will also pass it by reference.
Our new main() will be,
int main(int argc, char const ** argv){if(!argv[1]){std::cout << "You must invoke this program with an expression\n";return 1;}char const * text = argv[1];int result;if(eval(text, result)){std::cout << result << std::endl;}AST * root = nullptr;if(eval(text, root)){std::cout << result->eval() << std::endl;}else{std::cout << "There seems to be an error here: '" << text << "'\n";return 1;}return 0;}
We now pass an AST pointer to eval() instead of an integer.
We need to change the type in eval(),
bool eval(char const *& pos, int & result)bool eval(char const *& pos, AST *& node){if(!pos){return false;}return read_expression(pos, node) && !*pos;}
And this is our new read_expression(),
bool read_expression(char const *& pos, int & result, Operator previous_op)bool read_expression(char const *& pos, AST *& node, Operator previous_op){if(read_number(pos, node)){Operator op;while(read_operator(pos, op)){/** Precedence check.*/bool const op_less_previous = p(op) < p(previous_op);if(op_less_previous){--pos;/** This will break to the `return true` statement.*/break;}/** Suffix*/if(is_suffix_operator(op)){if(!compute_unary(op, result, result)){return false;}node = new ASTUnary(op, node);continue;}/** Associativity check.*/bool const op_equal_previous = p(op) == p(previous_op);bool const op_left_associativity = a(op) == Associativity::Left;if(op_equal_previous && op_left_associativity){--pos;break;}int num;if(!read_expression(pos, num, op))AST * rhs;if(!read_expression(pos, rhs, op)){return false;}if(!compute_binary(op, result, num, result)){return false;}node = new ASTBinary(op, node, rhs);}return true;}return false;}
The biggest change here is the removal of the calls to compute_binary()
and compute_unary(). Instead we construct either a new ASTBinary object
or a new ASTUnary object. This is where we build our AST. Since we take node
by reference we build the AST tree from the bottom up in-place. Notice how
node itself is always an argument to the constructor. node will always
point to the top object.
The last function to be modified is read_number(),
bool read_number(char const *& pos, int & num)bool read_number(char const *& pos, AST *& node){if(*pos == '('){++pos;if(!read_expression(pos, num) || *pos != ')')if(!read_expression(pos, node) || *pos != ')'){return false;}++pos;return true;}Operator op;if(read_prefix_operator(pos, op)){if(!read_expression(pos, num, op))if(!read_expression(pos, node, op)){return false;}if(!compute_unary(op, num, num)){return false;}node = new ASTUnary(op, node);return true;}num = 0;int num = 0;if(is_digit(*pos)){do{num *= 10;num += *pos - '0';++pos;} while(is_digit(*pos));node = new ASTNumber(num);return true;}return false;}
That's all we need to do. The evaluator will now build the AST for us.
Yes, I know. I don't delete.