This shows the general technique of recursive descent.
It evaluates expressions like
4 + (((3 + 5) * 6 + 8 + 4));
val = 64
Code:
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
/*
start->expr;
expr-> term | term + expr | term - expr
term-> factor * term | factor / term | factor
factor-> (expr) | num
num-> [0..N]
*/
enum { END_FILE, END_STATEMENT, PLUS, MINUS,
MULTIPLY, DIVIDE, LEFT_PARAN, RIGHT_PARAN, NUMBER};
struct Token {
int type;
int val;
};
void read_next_token();
bool match(int token_type);
int start();
int expr();
int term();
int factor();
Token next_token;
int main(void)
{
int val;
read_next_token();
val = start();
cout << "val = " << val << endl;
return 0;
}
void read_next_token()
{
int c;
next_token.type = END_FILE;
next_token.val = 0;
while((c = cin.get()) && isspace(c))
continue;
if (isdigit(c)) {
int n = 0;
cin.putback(c);
cin >> n;
next_token.type = NUMBER;
next_token.val = n;
return;
}
switch(c) {
case ';':
next_token.type = END_STATEMENT;
break;
case '+':
next_token.type = PLUS;
break;
case '-':
next_token.type = MINUS;
break;
case '*':
next_token.type = MULTIPLY;
break;
case '/':
next_token.type = DIVIDE;
break;
case '(':
next_token.type = LEFT_PARAN;
break;
case ')':
next_token.type = RIGHT_PARAN;
break;
}
}
bool match(int token_type)
{
bool ret;
if (next_token.type == token_type) {
read_next_token();
ret = true;
} else {
ret = false;
}
return ret;
}
int start()
{
int val = expr();
return val;
}
int expr()
{
int val = 0;
val = term();
switch(next_token.type) {
case PLUS:
match(PLUS);
val += expr();
break;
case MINUS:
match(MINUS);
val -= expr();
break;
default:
break;
}
return val;
}
int term()
{
int val;
val = factor();
switch(next_token.type) {
case MULTIPLY:
match(MULTIPLY);
val *= term();
break;
case DIVIDE:
match(DIVIDE);
val /= term();
break;
default:
break;
}
return val;
}
int factor()
{
int val = 0;
switch(next_token.type) {
case NUMBER:
val = next_token.val;
match(NUMBER);
break;
case LEFT_PARAN:
match(LEFT_PARAN);
val = expr();
match(RIGHT_PARAN);
break;
default:
break;
}
return val;
}