Node Visitor Example

ASTNode.cpp

// https://en.wikipedia.org/wiki/Recursive_descent_parser

#include <bits/stdc++.h>

/// Conditional const
/// cond_const<true,  Type>: const Type
/// cond_const<false, Type>: Type
template <bool Const, class Type> struct cond_const {
  typedef const Type type;
  typedef const Type *ptr;
};

template <class Type> struct cond_const<false, Type> {
  typedef Type type;
  typedef Type *ptr;
};

class ValueNode;
class UnaryOperationNode;
class BinaryOperationNode;

template <bool Const> class ASTNodeVisitorBase {
protected:
  using ValueNodePtr = typename cond_const<Const, ValueNode>::ptr;
  using UnaryOperationNodePtr =
      typename cond_const<Const, UnaryOperationNode>::ptr;
  using BinaryOperationNodePtr =
      typename cond_const<Const, BinaryOperationNode>::ptr;

public:
  virtual ~ASTNodeVisitorBase() = default;
  virtual void visit(ValueNodePtr TheValueNode);
  virtual void visit(UnaryOperationNodePtr TheUnaryOperationNode);
  virtual void visit(BinaryOperationNodePtr TheBinaryOperationNode);
};

using ConstASTNodeVisitor = ASTNodeVisitorBase<true>;
using ASTNodeVisitor = ASTNodeVisitorBase<false>;

class ASTNode {
public:
  virtual ~ASTNode() = default;
  virtual void accept(ASTNodeVisitor &Visitor) = 0;
  virtual void accept(ConstASTNodeVisitor &Visitor) const = 0;
};

class ValueNode : public ASTNode {
  std::string Token;

public:
  ValueNode(const std::string &Token) : Token(Token) {}
  const std::string &getToken() const { return Token; }
  std::string &getToken() { return Token; }

  void accept(ASTNodeVisitor &Visitor) override { Visitor.visit(this); }
  void accept(ConstASTNodeVisitor &Visitor) const override {
    Visitor.visit(this);
  }
};

class OperationNode : public ASTNode {
  char Operation;

public:
  OperationNode(char Operation) : Operation(Operation) {}
  char getOperation() const { return Operation; }
  char &getOperation() { return Operation; }

  virtual void accept(ASTNodeVisitor &Visitor) = 0;
  virtual void accept(ConstASTNodeVisitor &Visitor) const = 0;
};

class UnaryOperationNode : public OperationNode {
  std::unique_ptr<ASTNode> SubNode;

public:
  UnaryOperationNode(char Operation, std::unique_ptr<ASTNode> &&SubNode)
      : OperationNode(Operation), SubNode(std::move(SubNode)) {}
  const std::unique_ptr<ASTNode> &getSubNode() const { return SubNode; }
  std::unique_ptr<ASTNode> &getSubNode() { return SubNode; }

  void accept(ASTNodeVisitor &Visitor) override { Visitor.visit(this); }
  void accept(ConstASTNodeVisitor &Visitor) const override {
    Visitor.visit(this);
  }
};

class BinaryOperationNode : public OperationNode {
  std::unique_ptr<ASTNode> Left, Right;

public:
  BinaryOperationNode(char Operation, std::unique_ptr<ASTNode> &&Left,
                      std::unique_ptr<ASTNode> &&Right)
      : OperationNode(Operation), Left(std::move(Left)),
        Right(std::move(Right)) {}
  const std::unique_ptr<ASTNode> &getLeft() const { return Left; }
  const std::unique_ptr<ASTNode> &getRight() const { return Right; }
  std::unique_ptr<ASTNode> &getLeft() { return Left; }
  std::unique_ptr<ASTNode> &getRight() { return Right; }

  void accept(ASTNodeVisitor &Visitor) override { Visitor.visit(this); }
  void accept(ConstASTNodeVisitor &Visitor) const override {
    Visitor.visit(this);
  }
};

template <bool Const>
void ASTNodeVisitorBase<Const>::visit(ValueNodePtr TheValueNode) {
  // leaf
}
template <bool Const>
void ASTNodeVisitorBase<Const>::visit(
    UnaryOperationNodePtr TheUnaryOperationNode) {
  TheUnaryOperationNode->getSubNode()->accept(*this);
}
template <bool Const>
void ASTNodeVisitorBase<Const>::visit(
    BinaryOperationNodePtr TheBinaryOperationNode) {
  TheBinaryOperationNode->getLeft()->accept(*this);
  TheBinaryOperationNode->getRight()->accept(*this);
}

class Lexer {
  std::string Input;
  std::string Token;
  unsigned Idx;

public:
  Lexer(const std::string &Input) : Input(Input), Idx(0) { next(); }
  const std::string &getInput() const { return Input; }
  std::string getToken() const { return Token; }
  bool isFinished() const { return Idx >= Input.size() && Token.empty(); }
  void next() {
    Token = "";
    while (Idx < Input.size() && isspace(Input.at(Idx)))
      ++Idx;
    if (Idx >= Input.size())
      return;
    Token = Input.at(Idx++);
    if (!isdigit(Token.at(0)))
      return;
    while (Idx < Input.size() && isdigit(Input.at(Idx)))
      Token += Input.at(Idx++);
  }
};

namespace TokenTraits {
int precedence(const std::string &Operator) {
  if (Operator.size() != 1)
    return 0;
  switch (Operator[0]) {
  case '+':
  case '-':
    return 1;
  case '*':
  case '/':
  case '%':
    return 2;
  default:
    return 0;
  }
}
bool isBinaryOperator(const std::string &Operator) {
  if (Operator.size() != 1)
    return false;
  switch (Operator[0]) {
  case '+':
  case '-':
  case '*':
  case '/':
  case '%':
    return true;
  default:
    return false;
  }
}
bool isUnaryOperator(const std::string &Operator) {
  if (Operator.size() != 1)
    return false;
  switch (Operator[0]) {
  case '+':
  case '-':
    return true;
  default:
    return false;
  }
}
bool isNumber(const std::string &Token) {
  return (Token.size() && isdigit(Token[0]));
}
} // namespace TokenTraits

class Parser {
  Lexer TheLexer;

  void advance() {
    assert(TheLexer.isFinished() == false);
    TheLexer.next();
  }

  std::unique_ptr<ASTNode> parseExpression() {
    auto Expression = parseBinaryExpression(1);
    // ignore parse Assignment Operator or Conditional Operator
    return Expression;
  }
  std::unique_ptr<ASTNode> parseBinaryExpression(int MinPrecedence) {
    auto Expression = parseUnaryExpression();
    auto Token = TheLexer.getToken();
    int Precedence = TokenTraits::precedence(Token);
    for (; Precedence >= MinPrecedence; --Precedence) {
      for (;;) {
        Token = TheLexer.getToken();
        if (Token.empty() || TokenTraits::precedence(Token) != Precedence)
          break;
        advance();
        char Operator = Token[0];
        auto Right = parseBinaryExpression(Precedence + 1); // Left Recursive
        // auto Right = parseBinaryExpression(Precedence); // Right Recursive
        Expression = std::make_unique<BinaryOperationNode>(
            Operator, std::move(Expression), std::move(Right));
      }
    }
    return Expression;
  }
  std::unique_ptr<ASTNode> parseUnaryExpression() {
    auto Token = TheLexer.getToken();
    if (TokenTraits::isUnaryOperator(Token)) {
      advance();
      auto SubExpression = parseUnaryExpression();
      return std::make_unique<UnaryOperationNode>(Token[0],
                                                  std::move(SubExpression));
    }
    auto SubExpression = parseLeftHandSideExpression();
    return SubExpression;
  }
  std::unique_ptr<ASTNode> parseLeftHandSideExpression() {
    auto Expression = parsePrimaryExpression();
    // ignore other LeftHandSideExpression
    return Expression;
  }
  std::unique_ptr<ASTNode> parsePrimaryExpression() {
    auto Token = TheLexer.getToken();
    if (TokenTraits::isNumber(Token)) {
      advance();
      return std::make_unique<ValueNode>(Token);
    }
    if (Token == "(") {
      advance();
      auto Expression = parseExpression();
      Token = TheLexer.getToken();
      assert(Token == ")");
      advance();
      return Expression;
    }
    assert(false && "PrimaryExpression must be Number or Parentheses");
  }

public:
  Parser(const std::string &Input) : TheLexer(Input) {}
  std::unique_ptr<ASTNode> parse() {
    auto Root = parseExpression();
    assert(TheLexer.isFinished());
    return Root;
  }
};

class Printer : public ConstASTNodeVisitor {
  std::ostream &Out;

public:
  Printer(std::ostream &Out) : Out(Out) {}
  void visit(ValueNodePtr TheValueNode) override {
    Out << TheValueNode->getToken();
  }
  void visit(UnaryOperationNodePtr TheUnaryOperationNode) override {
    Out << "(" << TheUnaryOperationNode->getOperation();
    ConstASTNodeVisitor::visit(TheUnaryOperationNode);
    Out << ")";
  }
  void visit(BinaryOperationNodePtr TheBinaryOperationNode) override {
    Out << "(";
    TheBinaryOperationNode->getLeft()->accept(*this);
    Out << TheBinaryOperationNode->getOperation();
    TheBinaryOperationNode->getRight()->accept(*this);
    Out << ")";
  }
  void print(const ASTNode *Root) {
    Root->accept(*this);
    Out << '\n';
  }
};

class Calculator : public ConstASTNodeVisitor {
  std::stack<int, std::vector<int>> Stack;

public:
  void visit(ValueNodePtr TheValueNode) override {
    auto Ans = std::stoi(TheValueNode->getToken());
    Stack.emplace(Ans);
  }
  void visit(UnaryOperationNodePtr TheUnaryOperationNode) override {
    ConstASTNodeVisitor::visit(TheUnaryOperationNode);
    if (TheUnaryOperationNode->getOperation() == '-') {
      Stack.top() *= -1;
    }
  }
  void visit(BinaryOperationNodePtr TheBinaryOperationNode) override {
    ConstASTNodeVisitor::visit(TheBinaryOperationNode);
    int R = Stack.top();
    Stack.pop();
    int L = Stack.top();
    Stack.pop();
    switch (TheBinaryOperationNode->getOperation()) {
    case '+':
      Stack.emplace(L + R);
      break;
    case '-':
      Stack.emplace(L - R);
      break;
    case '*':
      Stack.emplace(L * R);
      break;
    case '/':
      Stack.emplace(L / R);
      break;
    case '%':
      Stack.emplace(L % R);
      break;
    }
  }
  int getAnswer(const ASTNode *Root) {
    Root->accept(*this);
    return Stack.top();
  }
};

int main() {
  std::string Input;
  while (std::getline(std::cin, Input)) {
    Parser TheParser(Input);
    auto Root = TheParser.parse();
    Printer ThePrinter(std::cout);
    ThePrinter.print(Root.get());
    std::cout << Calculator().getAnswer(Root.get()) << '\n';
  }
  return 0;
}

/*
-1+-1*-(7122*-1+-712222/3) + 2 - 3 / 4 + 5 * 6 - 7
( 12 + 5 ) * 6 + 10 / 2
2 * ( 3 + 4 ) * 5
2 - 3 / 4 + 5 * 6 - 7 % 8
2 + 3 * 4
3 * 4 / 2
( ( ( 2 - ( 3 / 4 ) ) + ( 5 * 6 ) ) - ( 7 % 8 ) )
6 / 3 * ( 1 - 4 ) + 3 - 8
12 + ( 3 * ( 20 / 4 ) - 8 ) * 6
15 + ( 4 - 7 % 3 ) * 8
10 / ( 2 - 7 ) + 5 % 3
10 / 2 - 7 + 5 % 3
*/