parser.cpp

#include <iostream>
#include <queue>
#include <stack>
#include <string>

enum TokenType {
  NUMBER,
  LBRAC,
  RBRAC,
  PLUS,
  MINUS,
  MUL,
  DIV,
  POW,
};

struct Token {
  TokenType type;
  std::string value;
};

struct Node {
  std::string op;
  Node *left, *right;

  void print(int indent = 0) {
    for (int i = 0; i < indent; i++)
      std::cout << ' ';
    std::cout << op << std::endl;
    if (left != nullptr)
      left->print(indent + 4);
    if (right != nullptr)
      right->print(indent + 4);
  }
};

Node *parse_num(std::queue<Token> &);
Node *parse_brac(std::queue<Token> &);
Node *parse_mul(std::queue<Token> &);
Node *parse_div(std::queue<Token> &);
Node *parse_minus(std::queue<Token> &);
Node *parse_plus(std::queue<Token> &);
Node *parse(std::queue<Token> &);

Node *parse_num(std::queue<Token> &tokens) {
  // possibily parse unary operators here
  if (!tokens.size() || tokens.front().type != NUMBER)
    throw;
  auto token = tokens.front();
  tokens.pop();
  return new Node{token.value, nullptr, nullptr}; // yeah somewhat weird that I'm putting the number in the op
}

Node *parse_brac(std::queue<Token> &tokens) {
  if (tokens.size() && tokens.front().type == LBRAC) {
    tokens.pop();
    auto ret = parse(tokens);
    if (!tokens.size() || tokens.front().type != RBRAC)
      throw;
    tokens.pop();
    return ret;
  }

  return parse_num(tokens);
}

Node *parse_pow(std::queue<Token> &tokens) {
  std::stack<Node *> st;
  st.push(parse_brac(tokens));
  while (tokens.size() && tokens.front().type == POW) {
    tokens.pop();
    st.push(parse_brac(tokens));
  }

  auto ret = st.top();
  for (st.pop(); st.size(); st.pop())
    ret = new Node{"^", st.top(), ret};
  return ret;
}

Node *parse_mul(std::queue<Token> &tokens) {
  auto ret = parse_pow(tokens);
  while (tokens.size() && tokens.front().type == MUL) {
    tokens.pop();
    ret = new Node{"*", ret, parse_pow(tokens)};
  }
  return ret;
}

Node *parse_div(std::queue<Token> &tokens) {
  auto ret = parse_mul(tokens);
  while (tokens.size() && tokens.front().type == DIV) {
    tokens.pop();
    ret = new Node{"/", ret, parse_mul(tokens)};
  }
  return ret;
}

Node *parse_minus(std::queue<Token> &tokens) {
  auto ret = parse_div(tokens);
  while (tokens.size() && tokens.front().type == MINUS) {
    tokens.pop();
    ret = new Node{"-", ret, parse_div(tokens)};
  }
  return ret;
}

Node *parse_plus(std::queue<Token> &tokens) {
  auto ret = parse_minus(tokens);
  while (tokens.size() && tokens.front().type == PLUS) {
    tokens.pop();
    ret = new Node{"+", ret, parse_minus(tokens)};
  }
  return ret;
}

Node *parse(std::queue<Token> &tokens) { return parse_plus(tokens); }

std::queue<Token> lex(std::string expr) {
  std::queue<Token> tokens;

  int i = 0;
  while (i < expr.size()) {
    if (isspace(expr[i])) {
      i++;
    } else if (expr[i] == '+') {
      tokens.push(Token{PLUS, "+"});
      i++;
    } else if (expr[i] == '-') {
      tokens.push(Token{MINUS, "-"});
      i++;
    } else if (expr[i] == '*') {
      tokens.push(Token{MUL, "*"});
      i++;
    } else if (expr[i] == '/') {
      tokens.push(Token{DIV, "/"});
      i++;
    } else if (expr[i] == '^') {
      tokens.push(Token{POW, "^"});
      i++;
    } else if (expr[i] == '(') {
      tokens.push(Token{LBRAC, "("});
      i++;
    } else if (expr[i] == ')') {
      tokens.push(Token{RBRAC, ")"});
      i++;
    } else if (isdigit(expr[i])) {
      std::string num;
      for (; i < expr.size() && isdigit(expr[i]); i++)
        num.push_back(expr[i]);
      tokens.push(Token{NUMBER, num});
    } else {
      throw;
    }
  }

  return tokens;
}

int main() {
  auto tokens = lex("5 - 2 - 3 * 10 + (1 - 2 + 3)^2^3^5 * 5 / 100 + 2");
  Node *node = parse(tokens);
  node->print();
}