fork(2) download
copy 
  1. #include <cctype>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <map>
  5. #include <string>
  6. #include <sstream>
  7. #include <vector>
  8.  
  9. namespace TinyCalc { 
  10.  
  11. // storage of variables
  12.  
  13. class Var {
  14.   private:
  15.     double _value;
  16.   public:
  17.     Var(): _value() { }
  18.     ~Var() = default;
  19.     double get() const { return _value; }
  20.     void set(double value) { _value = value; }
  21. };
  22.  
  23. typedef std::map<std::string, Var> VarTable;
  24.  
  25. // abstract syntax tree -> storage of "executable"
  26.  
  27. namespace AST {
  28.  
  29. class Expr {
  30.   protected:
  31.     Expr() = default;
  32.   public:
  33.     virtual ~Expr() = default;
  34.   public:
  35.     virtual double solve() const = 0;
  36. };
  37.  
  38. class ExprConst: public Expr {
  39.   private:
  40.     double _value;
  41.   public:
  42.     ExprConst(double value): Expr(), _value(value) { }
  43.     virtual ~ExprConst() = default;
  44.     virtual double solve() const { return _value; }
  45. };
  46.  
  47. class ExprVar: public Expr {
  48.   private:
  49.     Var *_pVar;
  50.   public:
  51.     ExprVar(Var *pVar): Expr(), _pVar(pVar) { }
  52.     virtual ~ExprVar() = default;
  53.     virtual double solve() const { return _pVar->get(); }
  54. };
  55.  
  56. class ExprUnOp: public Expr {
  57.   protected:
  58.     Expr *_pArg1;
  59.   protected:
  60.     ExprUnOp(Expr *pArg1): Expr(), _pArg1(pArg1) { }
  61.     virtual ~ExprUnOp() { delete _pArg1; }
  62. };
  63.  
  64. class ExprUnOpNeg: public ExprUnOp {
  65.   public:
  66.     ExprUnOpNeg(Expr *pArg1): ExprUnOp(pArg1) { }
  67.     virtual ~ExprUnOpNeg() = default;
  68.     virtual double solve() const
  69.     {
  70.       return -_pArg1->solve();
  71.     }
  72. };
  73.  
  74. class ExprBinOp: public Expr {
  75.   protected:
  76.     Expr *_pArg1, *_pArg2;
  77.   protected:
  78.     ExprBinOp(Expr *pArg1, Expr *pArg2):
  79.       Expr(), _pArg1(pArg1), _pArg2(pArg2)
  80.     { }
  81.     virtual ~ExprBinOp() { delete _pArg1; delete _pArg2; }
  82. };
  83.  
  84. class ExprBinOpAdd: public ExprBinOp {
  85.   public:
  86.     ExprBinOpAdd(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
  87.     virtual ~ExprBinOpAdd() = default;
  88.     virtual double solve() const
  89.     {
  90.       return _pArg1->solve() + _pArg2->solve();
  91.     }
  92. };
  93.  
  94. class ExprBinOpSub: public ExprBinOp {
  95.   public:
  96.     ExprBinOpSub(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
  97.     virtual ~ExprBinOpSub() = default;
  98.     virtual double solve() const
  99.     {
  100.       return _pArg1->solve() - _pArg2->solve();
  101.     }
  102. };
  103.  
  104. class ExprBinOpMul: public ExprBinOp {
  105.   public:
  106.     ExprBinOpMul(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
  107.     virtual ~ExprBinOpMul() = default;
  108.     virtual double solve() const
  109.     {
  110.       return _pArg1->solve() * _pArg2->solve();
  111.     }
  112. };
  113.  
  114. class ExprBinOpDiv: public ExprBinOp {
  115.   public:
  116.     ExprBinOpDiv(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
  117.     virtual ~ExprBinOpDiv() = default;
  118.     virtual double solve() const
  119.     {
  120.       return _pArg1->solve() / _pArg2->solve();
  121.     }
  122. };
  123.  
  124. } // namespace AST
  125.  
  126. // token class - produced in scanner, consumed in parser
  127. struct Token {
  128.   // tokens
  129.   enum Tk {
  130.     Plus, Minus, Star, Slash, LParen, RParen, Semicolon,
  131.     Number, Id,
  132.     EOT, Error
  133.   };
  134.   // token number
  135.   Tk tk;
  136.   // lexem as floating point number
  137.   double number;
  138.   // lexem as identifier
  139.   std::string id;
  140.  
  141.   // constructors.
  142.   explicit Token(Tk tk): tk(tk), number() { }
  143.   explicit Token(double number): tk(Number), number(number) { }
  144.   explicit Token(const std::string &id): tk(Id), number(), id(id) { }
  145. };
  146.  
  147. // the scanner - groups characters to tokens
  148. class Scanner {
  149.   private:
  150.     std::istream &_in;
  151.  
  152.   public:
  153.     // constructor.
  154.     Scanner(std::istream &in): _in(in) { }
  155.  
  156.     /* groups characters to next token until the first character
  157.      * which does not match (or end-of-file is reached).
  158.      */
  159.     Token scan()
  160.     {
  161.       char c;
  162.       // skip white space
  163.       do {
  164.         if (!(_in >> c)) return Token(Token::EOT);
  165.       } while (isspace(c));
  166.       // classify character and build token
  167.       switch (c) {
  168.         case '+': return Token(Token::Plus);
  169.         case '-': return Token(Token::Minus);
  170.         case '*': return Token(Token::Star);
  171.         case '/': return Token(Token::Slash);
  172.         case '(': return Token(Token::LParen);
  173.         case ')': return Token(Token::RParen);
  174.         case ';': return Token(Token::Semicolon);
  175.         default:
  176.           if (isdigit(c)) {
  177.             _in.unget(); double value; _in >> value;
  178.             return Token(value);
  179.           } else if (isalpha(c) || c == '_') {
  180.             std::string id(1, c);
  181.             while (_in >> c) {
  182.               if (isalnum(c) || c == '_') id += c;
  183.               else { _in.unget(); break; }
  184.             }
  185.             return Token(id);
  186.           } else {
  187.             _in.unget();
  188.             return Token(Token::Error);
  189.           }
  190.       }
  191.     }
  192. };
  193.  
  194. /* parser
  195.  *
  196.  * This is a recursive descent parser with a look-ahead of one symbol
  197.  * and without back-tracking.
  198.  * The parser implements the following grammar:
  199.  *
  200.  * program
  201.  *   : expr Semicolon program
  202.  *   | <empty>
  203.  *   ;
  204.  *
  205.  * expr
  206.  *   : addExpr
  207.  *   ;
  208.  * 
  209.  * addExpr
  210.  *   : mulExpr addExprRest
  211.  *   ;
  212.  *   
  213.  * addExprRest
  214.  *   : addOp mulExpr addExprRest
  215.  *   | <empty>
  216.  *   ;
  217.  *   
  218.  * mulExpr
  219.  *   : unaryExpr mulExprRest
  220.  *   ;
  221.  *   
  222.  * mulExprRest
  223.  *   : mulOp unaryExpr mulExprRest
  224.  *   | <empty>
  225.  *   ;
  226.  * 
  227.  * mulOp
  228.  *   : Star | Slash
  229.  *   ;
  230.  *   
  231.  * unaryExpr
  232.  *   : unOp unaryExpr
  233.  *   | primExpr
  234.  *   ;
  235.  * 
  236.  * unOp
  237.  *   : Plus | Minus
  238.  *   ;
  239.  *   
  240.  * primExpr
  241.  *   : Number
  242.  *   | Id
  243.  *   | LParen expr RParen
  244.  *   ;
  245.  */
  246. class Parser {
  247.   private:
  248.     Scanner _scanner;
  249.     VarTable &_varTable;
  250.     Token _lookAhead;
  251.  
  252.   private:
  253.     // constructor.
  254.     Parser(std::istream &in, VarTable &varTable):
  255.       _scanner(in), _varTable(varTable), _lookAhead(Token::EOT)
  256.     {
  257.       scan(); // load look ahead initially
  258.     }
  259.  
  260.     // calls the scanner to read the next look ahead token.
  261.     void scan() { _lookAhead = _scanner.scan(); }
  262.  
  263.     // consumes a specific token.
  264.     bool match(Token::Tk tk)
  265.     {
  266.       if (_lookAhead.tk != tk) {
  267.         std::cerr << "SYNTAX ERROR! Unexpected token!" << std::endl;
  268.         return false;
  269.       }
  270.       scan();
  271.       return true;
  272.     }
  273.  
  274.     // the rules:
  275.  
  276.     std::vector<AST::Expr*> parseProgram()
  277.     {
  278.       // right recursive rule
  279.       // -> can be done as iteration
  280.       std::vector<AST::Expr*> pExprs;
  281.       for (;;) {
  282.         if (AST::Expr *pExpr = parseExpr()) {
  283.           pExprs.push_back(pExpr);
  284.         } else break;
  285.         // special error checking for missing ';' (usual error)
  286.         if (_lookAhead.tk != Token::Semicolon) {
  287.           std::cerr << "SYNTAX ERROR: Semicolon expected!" << std::endl;
  288.           break;
  289.         }
  290.         scan(); // consume semicolon
  291.         if (_lookAhead.tk == Token::EOT) return pExprs;
  292.       }
  293.       // error handling
  294.       for (AST::Expr *pExpr : pExprs) delete pExpr;
  295.       pExprs.clear();
  296.       return pExprs;
  297.     }
  298.  
  299.     AST::Expr* parseExpr()
  300.     {
  301.       return parseAddExpr();
  302.     }
  303.  
  304.     AST::Expr* parseAddExpr()
  305.     {
  306.       if (AST::Expr *pExpr1 = parseMulExpr()) {
  307.         return parseAddExprRest(pExpr1);
  308.       } else return nullptr; // ERROR!
  309.     }
  310.  
  311.     AST::Expr* parseAddExprRest(AST::Expr *pExpr1)
  312.     {
  313.       // right recursive rule for left associative operators
  314.       // -> can be done as iteration
  315.       for (;;) {
  316.         switch (_lookAhead.tk) {
  317.           case Token::Plus:
  318.             scan(); // consume token
  319.             if (AST::Expr *pExpr2 = parseMulExpr()) {
  320.               pExpr1 = new AST::ExprBinOpAdd(pExpr1, pExpr2);
  321.             } else {
  322.               delete pExpr1;
  323.               return nullptr; // ERROR!
  324.             }
  325.             break;
  326.           case Token::Minus:
  327.             scan(); // consume token
  328.             if (AST::Expr *pExpr2 = parseMulExpr()) {
  329.               pExpr1 = new AST::ExprBinOpSub(pExpr1, pExpr2);
  330.             } else {
  331.               delete pExpr1;
  332.               return nullptr; // ERROR!
  333.             }
  334.             break;
  335.           case Token::Error:
  336.             std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
  337.             delete pExpr1;
  338.             return nullptr;
  339.           default: return pExpr1;
  340.         }
  341.       }
  342.     }
  343.  
  344.     AST::Expr* parseMulExpr()
  345.     {
  346.       if (AST::Expr *pExpr1 = parseUnExpr()) {
  347.         return parseMulExprRest(pExpr1);
  348.       } else return nullptr; // ERROR!
  349.     }
  350.  
  351.     AST::Expr* parseMulExprRest(AST::Expr *pExpr1)
  352.     {
  353.       // right recursive rule for left associative operators
  354.       // -> can be done as iteration
  355.       for (;;) {
  356.         switch (_lookAhead.tk) {
  357.           case Token::Star:
  358.             scan(); // consume token
  359.             if (AST::Expr *pExpr2 = parseUnExpr()) {
  360.               pExpr1 = new AST::ExprBinOpMul(pExpr1, pExpr2);
  361.             } else {
  362.               delete pExpr1;
  363.               return nullptr; // ERROR!
  364.             }
  365.             break;
  366.           case Token::Slash:
  367.             scan(); // consume token
  368.             if (AST::Expr *pExpr2 = parseUnExpr()) {
  369.               pExpr1 = new AST::ExprBinOpDiv(pExpr1, pExpr2);
  370.             } else {
  371.               delete pExpr1;
  372.               return nullptr; // ERROR!
  373.             }
  374.             break;
  375.           case Token::Error:
  376.             std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
  377.             delete pExpr1;
  378.             return nullptr;
  379.           default: return pExpr1;
  380.         }
  381.       }
  382.     }
  383.  
  384.     AST::Expr* parseUnExpr()
  385.     {
  386.       // right recursive rule right recursive operators
  387.       // -> must be done as recursion
  388.       switch (_lookAhead.tk) {
  389.         case Token::Plus:
  390.           scan(); // consume token
  391.           // as a unary plus has no effect it is simply ignored
  392.           return parseUnExpr();
  393.         case Token::Minus:
  394.           scan();
  395.           if (AST::Expr *pExpr = parseUnExpr()) {
  396.             return new AST::ExprUnOpNeg(pExpr);
  397.           } else return nullptr; // ERROR!
  398.         default:
  399.           return parsePrimExpr();
  400.       }
  401.     }
  402.  
  403.     AST::Expr* parsePrimExpr()
  404.     {
  405.       AST::Expr *pExpr = nullptr;
  406.       switch (_lookAhead.tk) {
  407.         case Token::Number:
  408.           pExpr = new AST::ExprConst(_lookAhead.number);
  409.           scan(); // consume token
  410.           break;
  411.         case Token::Id: {
  412.           Var &var = _varTable[_lookAhead.id]; // find or create
  413.           pExpr = new AST::ExprVar(&var);
  414.           scan(); // consume token
  415.         } break;
  416.         case Token::LParen:
  417.           scan(); // consume token
  418.           if (!(pExpr = parseExpr())) return nullptr; // ERROR!
  419.           if (!match(Token::RParen)) {
  420.             delete pExpr; return nullptr; // ERROR!
  421.           }
  422.           break;
  423.         case Token::EOT:
  424.           std::cerr << "SYNTAX ERROR: Premature EOF!" << std::endl;
  425.           break;
  426.         case Token::Error:
  427.           std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
  428.           break;
  429.         default:
  430.           std::cerr << "SYNTAX ERROR: Unexpected token!" << std::endl;
  431.       }
  432.       return pExpr;
  433.     }
  434.  
  435.   public:
  436.  
  437.     // the parser function
  438.     static std::vector<AST::Expr*> parse(
  439.       std::istream &in, VarTable &varTable)
  440.     {
  441.       Parser parser(in, varTable);
  442.       return parser.parseProgram();
  443.     }
  444. };
  445.  
  446. } // namespace TinyCalc
  447.  
  448. // a sample application
  449.  
  450. using namespace std;
  451. using namespace TinyCalc;
  452.  
  453. int main()
  454. {
  455.   // the program:
  456.   const char *sourceCode =
  457.     "1 + 2 * 3 / 4 - 5;\n"
  458.     "a + b;\n"
  459.     "a - b;\n"
  460.     "a * b;\n"
  461.     "a / b;\n"
  462.     "a * (b + 3);\n";
  463.   // the variables
  464.   const char *vars[] = { "a", "b" };
  465.   enum { nVars = sizeof vars / sizeof *vars };
  466.   // the data
  467.   const double data[][nVars] = {
  468.     { 4.0, 2.0 },
  469.     { 2.0, 4.0 },
  470.     { 10.0, 5.0 },
  471.     { 42, 6 * 7 }
  472.   };
  473.   // compile program
  474.   stringstream in(sourceCode);
  475.   VarTable varTable;
  476.   vector<AST::Expr*> program = Parser::parse(in, varTable);
  477.   if (program.empty()) {
  478.     cerr << "ERROR: Compile failed!" << endl;
  479.     string line;
  480.     if (getline(in, line)) {
  481.       cerr << "Text at error: '" << line << "'" << endl;
  482.     }
  483.     return 1;
  484.   }
  485.   // apply program to the data
  486.   enum { nDataSets = sizeof data / sizeof *data };
  487.   for (size_t i = 0; i < nDataSets; ++i) {
  488.     const char *sep = "";
  489.     cout << "Data Set:" << endl;
  490.     for (size_t j = 0; j < nVars; ++j, sep = ", ") {
  491.       cout << sep << vars[j] << ": " << data[i][j];
  492.     }
  493.     cout << endl;
  494.     // load data
  495.     for (size_t j = 0; j < nVars; ++j) varTable[vars[j]].set(data[i][j]);
  496.     // perform program
  497.     cout << "Compute:" << endl;
  498.     istringstream in(sourceCode);
  499.     for (const AST::Expr *pExpr : program) {
  500.       string line; getline(in, line);
  501.       cout << line << ": " << pExpr->solve() << endl;
  502.     }
  503.     cout << endl;
  504.   }
  505.   // clear the program
  506.   for (AST::Expr *pExpr : program) delete pExpr;
  507.   program.clear();
  508.   // done
  509.   return 0;  
  510. }
  511.  
Success #stdin #stdout 0s 16112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Data Set:
a: 4, b: 2
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: 2
a * b;: 8
a / b;: 2
a * (b + 3);: 20

Data Set:
a: 2, b: 4
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: -2
a * b;: 8
a / b;: 0.5
a * (b + 3);: 14

Data Set:
a: 10, b: 5
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 15
a - b;: 5
a * b;: 50
a / b;: 2
a * (b + 3);: 80

Data Set:
a: 42, b: 42
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 84
a - b;: 0
a * b;: 1764
a / b;: 1
a * (b + 3);: 1890
https://ideone.com/kPSDlD
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!