enum TokenType {
Plus,
Minus,
Multiply,
Divide,
Number,
OpenBracket,
CloseBracket
};
struct Token {
TokenType type;
std::string data;
// other useful things
};
std::vector<Token> lex(std::string input) {
std::unordered_map<char, TokenType> singles;
singles['+'] = TokenType::Plus;
singles['-'] = TokenType::Minus;
singles['('] = TokenType::OpenBracket;
singles[')'] = TokenType::CloseBracket;
singles['*'] = TokenType::Multiply;
singles['/'] = TokenType::Divide;
std::unordered_set<char> whitespace;
whitespace.insert(' ');
whitespace.insert('\t');
whitespace.insert('\r');
whitespace.insert('\n');
std::unordered_set<char> nums;
for(int i = 0; i < 10; i++)
nums.insert('0' + i);
std::vector<Token> out;
for(auto it = input.begin(); it != input.end(); ++it) {
if (singles.find(*it) != singles.end()) {
Token t;
t.type = singles[*it];
out.push_back(t);
continue;
}
if (whitespace.find(*it) != whitespace.end()) {
continue;
}
if (nums.find(*it) != nums.end()) {
Token t;
t.type = TokenType::Number;
while(nums.find(*it) != nums.end()) {
t.data.push_back(*it);
++it;
if (it == input.end())
break;
}
out.push_back(t);
continue;
}
// error
}
return out;
};
class Expression {
virtual ~Expression() {}
};
class BinaryExpression : public Expression {
public:
std::unique_ptr<Expression> lhs;
std::unique_ptr<Expression> rhs;
virtual char GetType() const = 0; // +,-,/,*
};
class MultiplyExpression : public BinaryExpression {
public:
virtual char GetType() const { return '*'; }
};
class DivideExpression : public BinaryExpression {
public:
virtual char GetType() const { return '/'; }
};
class PlusExpression : public BinaryExpression {
public:
virtual char GetType() const { return '+'; }
};
class SubExpression : public BinaryExpression {
public:
virtual char GetType() const { return '-'; }
};
class NumExpression : public Expression {
public:
unsigned int num;
};
class Parser {
std::vector<Token::iterator begin, end;
std::unique_ptr<Expression> operator()() {
return ParseMultiplicativeExpression();
}
void CheckedIncrement() {
++begin;
if (begin == end) // fuck
}
std::unique_ptr<Expression> ParseMultiplicativeExpression() {
// mul_expression ('*' '/') add_expression (left-associative)
// add_expression
auto lhs = ParseAdditiveExpression();
while(true) {
if (begin->type == TokenType::Multiply) {
CheckedIncrement();
auto rhs = ParseAdditiveExpression();
auto expr = make_unique<MulExpression>();
expr->lhs = lhs;
expr->rhs = rhs;
lhs = expr;
}
if (begin->type == TokenType::Divide) {
CheckedIncrement();
auto rhs = ParseAdditiveExpression();
auto expr = make_unique<DivideExpression>();
expr->lhs = lhs;
expr->rhs = rhs;
lhs = expr;
}
break; // not a valid mul expr anymore
}
return lhs;
}
std::unique_ptr<Expression> ParseAdditiveExpression() {
// primary_expression ('+' '-') add_expression (right-associative)
// primary_expression
auto lhs = ParsePrimaryExpression();
if (begin->type == TokenType::Plus) {
CheckedIncrement();
auto expr = make_unique<PlusExpression>();
auto rhs = ParseAdditiveExpression();
expr->lhs = lhs; expr->rhs = rhs;
return expr;
}
if (begin->type == TokenType::Minus) {
CheckedIncrement();
auto expr = make_unique<SubExpression>();
auto rhs = ParseAdditiveExpression();
expr->lhs = lhs; expr->rhs = rhs;
return expr;
}
// not avalid add expression
return lhs;
}
std::unique_ptr<Expression> ParsePrimaryExpression() {
if (begin->type == TokenType::Number) {
// parse number from data here
CheckedIncrement();
return make_unique<NumExpression>();
}
if (begin->type == TokenType::OpenBracket) {
CheckedIncrement();
auto expr = ParseMultiplicativeExpression();
if (begin->type != TokenType::CloseBracket) { } // fuck
CheckedIncrement();
return expr;
}
}
};
std::unique_ptr<Expression> Parse(std::vector<Token> tokens) {
Parser p;
p.begin = tokens.begin();
p.end = tokens.end();
return p();
}