comp2013 - arithmetic expression parser

expr.cpp

#include <iostream>
#include <memory>
#include <cctype>
#include <cassert>
#include "expr.h"

namespace {

expr::ptr read_number(std::istream &is);
expr::ptr read_factor(std::istream &is);
expr::ptr read_term(std::istream &is);
expr::ptr read_expr_(std::istream &is);

expr::ptr read_number(std::istream &is)
{
  assert(is.good());
  const auto ch = peek_next_char(is);
  if(!isnumber(ch)) throw "SYNTAX ERROR : expected number";
  is.ignore(1, ch);
  auto num = ch - '0';
  while(true) {
    const auto ch = peek_next_char(is);
    if(!isnumber(ch)) return expr::new_num(num);
    is.ignore(1, ch);
    num = num * 10 + (ch - '0');
  }
}

expr::ptr read_factor(std::istream &is)
{
  assert(is.good());
  const auto ch = peek_next_char(is);
  if(ch == '(') {
    // '(' <expr> ')'
    is.ignore(1, ch);
    const auto root = read_expr_(is);
    const auto end = peek_next_char(is);
    if(end != ')') throw "SYNTAX ERROR : expected ')'";
    is.ignore(1, ch);
    return root;
  } else {
    // <number>
    return read_number(is);
  }
}

expr::ptr read_term(std::istream &is)
{
  assert(is.good());
  auto root = read_factor(is);
  while(true) {
    // <factor> [(*|/) <factor>]
    const auto op = peek_next_char(is);
    if(op != '*' && op != '/') break;
    is.ignore(1, op);
    const auto rhs = read_factor(is);
    const auto e = expr::new_op(op);
    e->update_lhs(root)->update_rhs(rhs);
    root = e;
  }
  return root;
}

expr::ptr read_expr_(std::istream &is)
{
  assert(is.good());
  const auto ch = peek_next_char(is);
  const auto is_minus = (ch == '-');
  if(is_minus) is.ignore(1, ch);
  auto root = read_term(is);
  if(is_minus) {
    const auto e = expr::new_op('*');
    const auto rhs = expr::new_num(-1);
    e->update_lhs(root)->update_rhs(rhs);
    root = e;
  }
  while(true) {
    // <term> [(+|-) <term>]
    const auto op = peek_next_char(is);
    if(op != '+' && op != '-') break;
    is.ignore(1, op);
    const auto rhs = read_term(is);
    const auto e = expr::new_op(op);
    e->update_lhs(root)->update_rhs(rhs);
    root = e;
  }
  return root;
}

}

int peek_next_char(std::istream &is)
{
  assert(is.good());
  while(true) {
    if(is.eof()) return EOF;
    char ch = is.peek();
    if(isblank(ch)) {
      is.get(ch);
      continue;
    }
    if(is.fail()) throw "FATAL : failed to read character";
    return iscntrl(ch) ? EOL : ch;
  }
}

int get_next_char(std::istream &is)
{
  assert(is.good());
  const auto ch = peek_next_char(is);
  is.ignore(1, ch);
  return ch;
}

expr::ptr read_expr(std::istream &is)
{
  assert(is.good());
  const auto root = read_expr_(is);
  const auto ch = peek_next_char(is);
  if(ch != EOL && ch != EOF) throw "SYNTAX ERROR : unexpected char";
  assert(root != nullptr);
  return root;
}

expr.h

#ifndef EXPR_H_
#define EXPR_H_

#include <iostream>
#include <cassert>

#define EOL -2

inline bool isoperator(const int ch)
{
  return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

class expr
{
public:
  using ptr = std::shared_ptr<expr>;
  enum class type
  {
    OPERATOR,
    NUMBER,
  };

  expr(const type t, const int val):t_(t), val_(val)
  {
  }

  static ptr new_op(const int op)
  {
    assert(isoperator(op));
    return std::make_shared<expr>(type::OPERATOR, op);
  }

  static ptr new_num(const int num)
  {
    return std::make_shared<expr>(type::NUMBER, num);
  }

  int eval() const
  {
    if(t_ == type::NUMBER) return val_;
    switch(val_) {
    case '+': return lhs_->eval() + rhs_->eval();
    case '-': return lhs_->eval() - rhs_->eval();
    case '*': return lhs_->eval() * rhs_->eval();
    case '/': return lhs_->eval() / rhs_->eval();
    default:
      assert(0 && "reached forbidden area");
    }
  }

  expr *update_lhs(ptr lhs)
  {
    assert(lhs_ != nullptr);
    lhs_ = lhs;
    return this;
  }
  expr *update_rhs(ptr rhs)
  {
    assert(rhs_ != nullptr);
    rhs_ = rhs;
    return this;
  }

private:
  type t_;
  int val_;
  ptr lhs_; // left hand side
  ptr rhs_; // right hand side
};

expr::ptr read_expr(std::istream &is);
int peek_next_char(std::istream &is);
int get_next_char(std::istream &is);


#endif

shell.cpp

#include <iostream>
#include "expr.h"

int main()
{
  while(true) {
    std::cout << "> ";
    try {
      if(peek_next_char(std::cin) == EOF) break;
      const auto root = read_expr(std::cin);
      std::cout << std::endl << "--> " << root->eval() << std::endl;
    } catch(const char *msg) {
      std::cout << msg << std::endl;
    }
    std::cout << std::endl;
    while(get_next_char(std::cin) != EOL);
  }
  return 0;
}

test.cpp

#include <iostream>
#include <sstream>
#include <string>
#include "expr.h"

int main()
{
  const auto cases_pass = {
    std::make_pair("12*3 + 3*4 - 10", 38),
    std::make_pair(" 12*(3+13)-10", 182),
    std::make_pair(" - 555", -555),
    std::make_pair("1 + 2  * 3", 7),
    std::make_pair("1 + 2*3 / 2", 4),
    std::make_pair("(1+2) *3  ", 9),
    std::make_pair("-(-1+5) ", -4),
    std::make_pair("-(5) ", -5),
    std::make_pair("-(-(5)) ", 5),
    std::make_pair("((50)) ", 50),
  };
  const auto cases_fail = {
    std::make_pair(" -  ", "SYNTAX ERROR : expected number"),
    std::make_pair("+4", "SYNTAX ERROR : expected number"),
    std::make_pair("++4", "SYNTAX ERROR : expected number"),
    std::make_pair("( 43   + ", "SYNTAX ERROR : expected number"),
    std::make_pair("( 43  ", "SYNTAX ERROR : expected ')'"),
    std::make_pair("5( ", "SYNTAX ERROR : unexpected char"),
    std::make_pair("5 + -4", "SYNTAX ERROR : expected number"),
  };

  // test for correct cases
  for(const auto &kv : cases_pass) {
    const auto query = kv.first;
    const auto expected = kv.second;
    std::istringstream iss(query);
    try {
      const auto e = read_expr(iss);
      const auto ret = e->eval();
      if(ret == expected) {
        std::cout << "[PASSED] " << query << " => " << expected << std::endl;
      } else {
        std::cout << "[FAILED] " << query << " ~> "
                  << "expected " << expected << " "
                  << "but " << ret << std::endl;
      }
    } catch(const char *msg) {
        std::cout << "[FAILED] " << query << " ~> "
                  << "expected " << expected << " "
                  << "but " << msg << std::endl;
    }
  }

  // test for invalid cases
  for(const auto &kv : cases_fail) {
    const auto query = kv.first;
    const auto expected = kv.second;
    std::istringstream iss(query);
    try {
      const auto e = read_expr(iss);
      std::cout << "[FAILED] " << query << " ~> " << expected << std::endl;
    } catch(const char *msg) {
      if(strcmp(msg, expected) == 0) {
        std::cout << "[PASSED] " << query << " => " << expected << std::endl;
      } else {
        std::cout << "[FAILED] " << query << " ~> " << expected << std::endl;
      }
    }
  }
  return 0;
}