Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 4th, 2012  |  syntax: None  |  size: 4.99 KB  |  views: 37  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. enum TokenType {
  2.     Plus,
  3.     Minus,
  4.     Multiply,
  5.     Divide,
  6.     Number,
  7.     OpenBracket,
  8.     CloseBracket
  9. };
  10. struct Token {
  11.     TokenType type;
  12.     std::string data;
  13.     // other useful things
  14. };
  15. std::vector<Token> lex(std::string input) {
  16.     std::unordered_map<char, TokenType> singles;
  17.     singles['+'] = TokenType::Plus;
  18.     singles['-'] = TokenType::Minus;
  19.     singles['('] = TokenType::OpenBracket;
  20.     singles[')'] = TokenType::CloseBracket;
  21.     singles['*'] = TokenType::Multiply;
  22.     singles['/'] = TokenType::Divide;
  23.     std::unordered_set<char> whitespace;
  24.     whitespace.insert(' ');
  25.     whitespace.insert('\t');
  26.     whitespace.insert('\r');
  27.     whitespace.insert('\n');
  28.     std::unordered_set<char> nums;
  29.     for(int i = 0; i < 10; i++)
  30.         nums.insert('0' + i);
  31.     std::vector<Token> out;
  32.     for(auto it = input.begin(); it != input.end(); ++it) {
  33.         if (singles.find(*it) != singles.end()) {
  34.             Token t;
  35.             t.type = singles[*it];
  36.             out.push_back(t);
  37.             continue;
  38.         }
  39.         if (whitespace.find(*it) != whitespace.end()) {
  40.             continue;
  41.         }
  42.         if (nums.find(*it) != nums.end()) {
  43.             Token t;
  44.             t.type = TokenType::Number;
  45.             while(nums.find(*it) != nums.end()) {
  46.                 t.data.push_back(*it);
  47.                 ++it;
  48.                 if (it == input.end())
  49.                     break;
  50.             }
  51.             out.push_back(t);
  52.             continue;
  53.         }
  54.         // error
  55.     }
  56.     return out;
  57. };
  58. class Expression {
  59.     virtual ~Expression() {}
  60. };
  61. class BinaryExpression : public Expression {
  62. public:
  63.      std::unique_ptr<Expression> lhs;
  64.      std::unique_ptr<Expression> rhs;
  65.      virtual char GetType() const = 0; // +,-,/,*
  66. };
  67. class MultiplyExpression : public BinaryExpression {
  68. public:
  69.     virtual char GetType() const { return '*'; }
  70. };
  71. class DivideExpression : public BinaryExpression {
  72. public:
  73.     virtual char GetType() const { return '/'; }
  74. };
  75. class PlusExpression : public BinaryExpression {
  76. public:
  77.     virtual char GetType() const { return '+'; }
  78. };
  79. class SubExpression : public BinaryExpression {
  80. public:
  81.     virtual char GetType() const { return '-'; }
  82. };
  83. class NumExpression : public Expression {
  84. public:
  85.     unsigned int num;
  86. };
  87. class Parser {
  88.     std::vector<Token::iterator begin, end;
  89.     std::unique_ptr<Expression> operator()() {
  90.         return ParseMultiplicativeExpression();
  91.     }
  92.     void CheckedIncrement() {
  93.         ++begin;
  94.         if (begin == end) // fuck
  95.     }
  96.     std::unique_ptr<Expression> ParseMultiplicativeExpression() {
  97.         // mul_expression ('*' '/') add_expression (left-associative)
  98.         // add_expression
  99.         auto lhs = ParseAdditiveExpression();
  100.         while(true) {
  101.             if (begin->type == TokenType::Multiply) {
  102.                 CheckedIncrement();
  103.                 auto rhs = ParseAdditiveExpression();
  104.                 auto expr = make_unique<MulExpression>();
  105.                 expr->lhs = lhs;
  106.                 expr->rhs = rhs;
  107.                 lhs = expr;
  108.             }
  109.             if (begin->type == TokenType::Divide) {
  110.                 CheckedIncrement();
  111.                 auto rhs = ParseAdditiveExpression();
  112.                 auto expr = make_unique<DivideExpression>();
  113.                 expr->lhs = lhs;
  114.                 expr->rhs = rhs;
  115.                 lhs = expr;
  116.             }
  117.             break; // not a valid mul expr anymore
  118.         }
  119.         return lhs;
  120.     }
  121.     std::unique_ptr<Expression> ParseAdditiveExpression() {
  122.         // primary_expression ('+' '-') add_expression (right-associative)
  123.         // primary_expression
  124.         auto lhs = ParsePrimaryExpression();
  125.         if (begin->type == TokenType::Plus) {
  126.             CheckedIncrement();
  127.             auto expr = make_unique<PlusExpression>();
  128.             auto rhs = ParseAdditiveExpression();
  129.             expr->lhs = lhs; expr->rhs = rhs;
  130.             return expr;
  131.         }
  132.         if (begin->type == TokenType::Minus) {
  133.             CheckedIncrement();
  134.             auto expr = make_unique<SubExpression>();
  135.             auto rhs = ParseAdditiveExpression();
  136.             expr->lhs = lhs; expr->rhs = rhs;
  137.             return expr;
  138.         }
  139.         // not avalid add expression
  140.         return lhs;
  141.     }
  142.     std::unique_ptr<Expression> ParsePrimaryExpression() {
  143.         if (begin->type == TokenType::Number) {          
  144.             // parse number from data here
  145.             CheckedIncrement();
  146.             return make_unique<NumExpression>();
  147.         }
  148.         if (begin->type == TokenType::OpenBracket) {
  149.             CheckedIncrement();
  150.             auto expr = ParseMultiplicativeExpression();
  151.             if (begin->type != TokenType::CloseBracket) { } // fuck
  152.             CheckedIncrement();
  153.             return expr;
  154.         }
  155.     }
  156. };
  157. std::unique_ptr<Expression> Parse(std::vector<Token> tokens) {
  158.     Parser p;
  159.     p.begin = tokens.begin();
  160.     p.end = tokens.end();
  161.     return p();
  162. }