四則演算(+剰余)の式をスタックマシンで計算するプログラム

expr_calc.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>

////////////////////// Util //////////////////////

void *xmalloc(size_t size) {
  void *ptr = malloc(size);

  if (ptr == NULL) {
    fprintf(stderr, "[Fatal Error] Failed to allocate memory\n");
    exit(EXIT_FAILURE);
  }

  return ptr;
}

void xfree(void *ptr) {
  free(ptr);
}

#define WHITE_SPACE_CHAR (-2)
#define UNKOWN_CHAR (-3)

int char_to_token(char);
bool check_all_chars_in_expr_is_valid(const char *expr) {
  size_t expr_len = strlen(expr);
  int paren_depth = 0;

  for (size_t i = 0; i < expr_len; i++) {
    if (char_to_token(expr[i]) == UNKOWN_CHAR) {
      return false;
    }
  }

  return true;
}

bool check_paren_balance_ok(const char *expr) {
  size_t expr_len = strlen(expr);
  int paren_depth = 0;

  for (size_t i = 0; i < expr_len; i++) {
    char c = expr[i];
    if (c == '(') {
      paren_depth++;
    } else if (c == ')') {
      paren_depth--;
      if (paren_depth < 0) { // too many rparens
        return false;
      }
    }
  }

  return paren_depth == 0 ? true : false;
}

bool validate_expr(const char *expr) {
  size_t expr_len = strlen(expr);
  return check_all_chars_in_expr_is_valid(expr) && check_paren_balance_ok(expr);
}

//////////////////////// Vector ////////////////////////

typedef struct {
  void **data;
  size_t capacity;
  size_t len;
} Vector;

#define VECTOR_DEFAULT_CAPACITY 16

#define VecForeachWithType(vec, T, loop_val, loop_body) \
  for (size_t fe_loop_counter_ ## vec = 0; fe_loop_counter_ ## vec < vec->len; fe_loop_counter_ ## vec ++) { \
    T loop_val = vec->data[fe_loop_counter_ ## vec]; \
    loop_body; \
  }

#define VecForeach(vec, loop_val, loop_body) VecForeachWithType(vec, void*, loop_val, loop_body)

Vector *new_vec_with(size_t capacity) {
  Vector *v = xmalloc(sizeof(Vector));
  v->data = xmalloc(sizeof(void *) * capacity);
  v->capacity = capacity;
  v->len = 0;
  return v;
}

Vector *new_vec() { return new_vec_with(VECTOR_DEFAULT_CAPACITY); }

void vec_expand(Vector *v, size_t size) {
  if (v->len < size) {
    v->capacity = size;
    v->len = size;
    v->data = realloc(v->data, sizeof(void *) * v->capacity);
  }
}

void vec_push(Vector *v, void *elem) {
  if (v->len == v->capacity) {
    v->capacity *= 2;
    v->data = realloc(v->data, sizeof(void *) * v->capacity);
  }
  v->data[v->len++] = elem;
}

void vec_pushi(Vector *v, int val) { vec_push(v, (void *)(intptr_t)val); }
void vec_pushlli(Vector *v, long long int val) { vec_push(v, (void *)val); }

void *vec_pop(Vector *v) {
  assert(v->len);
  return v->data[--v->len];
}

void *vec_last(Vector *v) {
  assert(v->len);
  return v->data[v->len - 1];
}

bool vec_contains(Vector *v, void *elem) {
  for (size_t i = 0; i < v->len; i++) {
    if (v->data[i] == elem) {
      return true;
    }
  }
  return false;
}

bool vec_union1(Vector *v, void *elem) {
  if (vec_contains(v, elem)) {
    return false;
  }
  vec_push(v, elem);
  return true;
}

void *vec_get(Vector *v, size_t idx) {
  assert(idx < v->len);
  return v->data[idx];
}

Vector *vec_dup(Vector *v) {
  Vector *vec = new_vec();
  for (size_t i = 0; i < v->len; i++) {
    vec_push(vec, v->data[i]);
  }
  return vec;
}

void vec_append(Vector *v1, Vector *v2) {
  VecForeach(v2, e, { vec_push(v1, e); })
}

// Element must not be pointer. It will leak.
void free_vec(Vector *v) {
  xfree(v->data);
  xfree(v);
}

/////////////////// Stack ///////////////////

#define STACK_DEFAULT_CAPCITY (1<<5)

typedef struct {
  int *stack;
  int count;
  int capacity;
} Stack;

Stack *new_Stack(void) {
  Stack *stack = xmalloc(sizeof(Stack));

  stack->count = 0;
  stack->capacity = STACK_DEFAULT_CAPCITY;
  stack->stack = xmalloc(sizeof(int) * stack->capacity);

  return stack;
}

void free_Stack(Stack *stack) {
  xfree(stack->stack);
  xfree(stack);
}

void push_Stack(Stack *stack, int val) {
  if (!(stack->count + 1 < stack->capacity)) { // capacity NG
    stack->capacity *= 2;
    stack->stack = realloc(stack->stack, sizeof(int) * stack->capacity);
  }

  stack->stack[stack->count++] = val;
}

int isEmpty_Stack(Stack *stack) {
  return stack->count == 0;
}

int pop_Stack(Stack *stack) {
  assert(!isEmpty_Stack(stack));
  return stack->stack[--stack->count];
}

///////////////////////// VM /////////////////////////

typedef enum {
  OpPush,
  OpPop,
  OpAdd,
  OpSub,
  OpMul,
  OpDiv,
  OpMod,
  OpPrint,
  OpDup,
} Opcode;

void run(Vector *code) {
  Stack *stack = new_Stack();

  for (size_t pc = 0; pc < code->len;) {
    int op = (intptr_t)code->data[pc++];

    switch (op) {
      case OpPush: {
                     int val = (intptr_t)code->data[pc++];
                     push_Stack(stack, val);
                     break;
                   }
      case OpPop: {
                    (void)pop_Stack(stack);
                    break;
                  }
      case OpAdd: {
                    int r = pop_Stack(stack);
                    int l = pop_Stack(stack);
                    push_Stack(stack, l + r);
                    break;
                  }
      case OpSub: {
                    int r = pop_Stack(stack);
                    int l = pop_Stack(stack);
                    push_Stack(stack, l - r);
                    break;
                  }
      case OpMul: {
                    int r = pop_Stack(stack);
                    int l = pop_Stack(stack);
                    push_Stack(stack, l * r);
                    break;
                  }
      case OpDiv: {
                    int r = pop_Stack(stack);
                    int l = pop_Stack(stack);
                    push_Stack(stack, l / r);
                    break;
                  }
      case OpMod: {
                    int r = pop_Stack(stack);
                    int l = pop_Stack(stack);
                    push_Stack(stack, l % r);
                    break;
                  }
      case OpPrint: {
                      int val = pop_Stack(stack);
                      printf("%d\n", val);
                      break;
                    }
      case OpDup: {
                    int val = pop_Stack(stack);
                    push_Stack(stack, val);
                    push_Stack(stack, val);
                    break;
                  }
    }
  }

  free_Stack(stack);
}

void print_Opcodes(Vector *code) {
  for (size_t pc = 0; pc < code->len;) {
    int op = (intptr_t)code->data[pc++];

    switch (op) {
      case OpPush: {
                     int val = (intptr_t)code->data[pc++];
                     printf("[%ld] OpPush<%d>\n", pc - 1, val);
                     break;
                   }
      case OpPop: {
                    printf("[%ld] OpPop\n", pc);
                    break;
                  }
      case OpAdd: {
                    printf("[%ld] OpAdd\n", pc);
                    break;
                  }
      case OpSub: {
                    printf("[%ld] OpSub\n", pc);
                    break;
                  }
      case OpMul: {
                    printf("[%ld] OpMul\n", pc);
                    break;
                  }
      case OpDiv: {
                    printf("[%ld] OpDiv\n", pc);
                    break;
                  }
      case OpMod: {
                    printf("[%ld] OpMod\n", pc);
                    break;
                  }
      case OpPrint: {
                      printf("[%ld] OpPrint\n", pc);
                      break;
                    }
      case OpDup: {
                    printf("[%ld] OpDup\n", pc);
                    break;
                  }
    }
  }
}

#define RUN_CODE(...) \
  do { \
    int code[] = { __VA_ARGS__ }; \
    size_t code_len = sizeof(code) / sizeof(code[0]); \
    Vector *vec = new_vec(); \
    for (int i = 0; i < code_len; i++) { vec_push(vec, (void*)(intptr_t)code[i]); } \
    run(vec); \
  } while (0)

//////////////////////// Tokenizer ////////////////////////

typedef enum {
  IntToken,
  AddToken,
  SubToken,
  MulToken,
  DivToken,
  ModToken,
  LparenToken,
  RparenToken,
} TokenType;

int char_to_token(char ch) {
  if (ch == '+') {
    return AddToken;
  } else if (ch == '-') {
    return SubToken;
  } else if (ch == '*') {
    return MulToken;
  } else if (ch == '/') {
    return DivToken;
  } else if (ch == '%') {
    return ModToken;
  } else if (ch == '(') {
    return LparenToken;
  } else if (ch == ')') {
    return RparenToken;
  } else if ('0' <= ch && ch <= '9') {
    return -1;
  } else if (ch == ' ') {
    return WHITE_SPACE_CHAR;
  } else {
    return UNKOWN_CHAR;
  }
}

typedef struct {
  TokenType type;
  int val;
} Token;

Token *new_Token(TokenType type) {
  Token *token = xmalloc(sizeof(Token)); 
  token->type = type;
  token->val = 0;
  return token;
}

Token *new_Token_with_val(TokenType type, int val) {
  Token *token = xmalloc(sizeof(Token)); 
  token->type = type;
  token->val = val;
  return token;
}

void free_Token(Token *token) {
  free(token);
}

void print_token(Token *token) {
  switch (token->type) {
    case IntToken: {
                     printf("IntToken<%d>", token->val);
                     break;
                   }
    case AddToken: {
                     printf("AddToken");
                     break;
                   }
    case SubToken: {
                     printf("SubToken");
                     break;
                   }
    case MulToken: {
                     printf("MulToken");
                     break;
                   }
    case DivToken: {
                     printf("DivToken");
                     break;
                   }
    case ModToken: {
                     printf("ModToken");
                     break;
                   }
    case LparenToken: {
                        printf("LparenToken");
                        break;
                      }
    case RparenToken: {
                        printf("RparenToken");
                        break;
                      }
  }
}

#define PRINT_TOKENS true

Vector *tokenize(const char *expr, const size_t expr_len) {
  Vector *tokens = new_vec();

  for (size_t idx = 0; idx < expr_len;) {
    char ch = expr[idx];
    int token = char_to_token(ch);
    if (token >= 0) {
      vec_push(tokens, new_Token(token));
      idx++;
    } else if (token == -1) { // read number
      int val = 0;
      do {
        val *= 10;
        int v = expr[idx++] - '0';
        val += v;
      } while (char_to_token(expr[idx]) == -1);
      vec_push(tokens, new_Token_with_val(IntToken, val));
    } else if (token == WHITE_SPACE_CHAR || token == UNKOWN_CHAR) { // skip space or unkown token
      idx++;
    }
  }

  if (PRINT_TOKENS) {
    printf("Tokens: { ");
    int count = 0;
    VecForeachWithType(tokens, Token *, token, {
        if (count++ > 0) {
          printf(", ");
        }
        print_token(token);
    });
    printf("}\n");
  }

  return tokens;
}

//////////////////////// Parser ////////////////////////

typedef enum {
  Node,
  Leaf
} ExprNodeType;

typedef struct ExprNode {
  ExprNodeType type;
  Token *token;
  // Node
  struct ExprNode *lhs;
  struct ExprNode *rhs;
} ExprNode;

ExprNode *new_ExprNode(Token *token) {
  ExprNode *node = xmalloc(sizeof(ExprNode));

  if (token == IntToken) {
    node->type = Leaf;
  } else {
    node->type = Node;
  }

  node->token = token;
  node->lhs = NULL;
  node->rhs = NULL;

  return node;
}

int get_pos_op_idx(Vector *tokens) {
  int pos = -1;
  int current_priority = INT_MAX;
  int priority;
  int paren_depth = 0;

  for (int i = 0; i < tokens->len; i++) {
    Token *token = vec_get(tokens, i);
    switch (token->type) {
      case AddToken: { priority = 2; break; }
      case SubToken: { priority = 2; break; }
      case MulToken: { priority = 3; break; }
      case DivToken: { priority = 3; break; }
      case ModToken: { priority = 3; break; }
      case LparenToken: { paren_depth++; continue; }
      case RparenToken: { paren_depth--; continue; }
      default: continue;
    }

    if (paren_depth == 0 && priority <= current_priority) {
      current_priority = priority;
      pos = i;
    }
  }

  return pos;
}

Vector *slice_vec(Vector *v, int begin, int end) {
  Vector *ret = new_vec();

  for (int i = begin; i <= end && i < v->len; i++) {
    vec_push(ret, vec_get(v, i));
  }

  return ret;
}

Vector *remove_most_outer_paren_token(Vector *tokens) {
  int begin = 0;
  int end = tokens->len;
  Vector *ret = new_vec();

  Token *first_token = (Token*)vec_get(tokens, 0);
  Token *last_token = (Token*)vec_get(tokens, tokens->len - 1);
  if (first_token->type == LparenToken && last_token->type == RparenToken) {
    begin++;
    end--;
    free_Token(first_token);
    free_Token(last_token);
  }

  for (int i = begin; i < end && i < tokens->len; i++) {
    vec_push(ret, vec_get(tokens, i));
  }

  return ret;
}

#define DEBUG_EXPR_TO_NODE false

ExprNode *expr_to_node(Vector *tokens) {
  ExprNode *node;

  tokens = remove_most_outer_paren_token(tokens);

  int op_pos = get_pos_op_idx(tokens);
  if (op_pos == -1) { // no op
    node = new_ExprNode(vec_get(tokens, 0));
  } else {
    Token *op_token = vec_get(tokens, op_pos);
    int lhs_end = op_pos - 1;
    int rhs_begin = op_pos + 1;
    Vector *lhs_tokens = slice_vec(tokens, 0, lhs_end);
    Vector *rhs_tokens = slice_vec(tokens, rhs_begin, tokens->len);

    if (PRINT_TOKENS && DEBUG_EXPR_TO_NODE) {
      printf("LHS_TOKENS: ");
      int count = 0;
      VecForeachWithType(lhs_tokens, Token *, token, {
          if (count++ > 0) {
            printf(", ");
          }
          print_token(token);
      });
      printf("\n");

      count = 0;
      printf("RHS_TOKENS: ");
      VecForeachWithType(rhs_tokens, Token *, token, {
          if (count++ > 0) {
            printf(", ");
          }
          print_token(token);
      });
      printf("\n");
    }

    node = new_ExprNode(op_token);
    node->lhs = expr_to_node(lhs_tokens);
    node->rhs = expr_to_node(rhs_tokens);
  }

  return node;
}

#define PRINT_TOKEN_IN_TRAVERSE false

void traverse_ExprNode_postorder(ExprNode *node, Vector *ret) {
  if (node->lhs) {
    traverse_ExprNode_postorder(node->lhs, ret);
  }
  if (node->rhs) {
    traverse_ExprNode_postorder(node->rhs, ret);
  }

  Token *token = node->token;
  switch (token->type) {
    case IntToken: {
                     vec_pushi(ret, OpPush);
                     vec_pushi(ret, token->val);
                     break;
                   }
    case AddToken: { vec_pushi(ret, OpAdd); break; }
    case SubToken: { vec_pushi(ret, OpSub); break; }
    case MulToken: { vec_pushi(ret, OpMul); break; }
    case DivToken: { vec_pushi(ret, OpDiv); break; }
    case ModToken: { vec_pushi(ret, OpMod); break; }
    default: break;
  }

  if (PRINT_TOKEN_IN_TRAVERSE) {
    print_token(node->token);
    printf(" ");
  }
}

Vector *parser(Vector *tokens) {
  ExprNode *expr_node = expr_to_node(tokens);
  Vector *result = new_vec();
  traverse_ExprNode_postorder(expr_node, result);
  return result;
}

void calc_expr(const char *expr) {
  if (!validate_expr(expr)) {
    fprintf(stderr, "Given expr is invalid\n");
    return;
  }

  const size_t expr_len = strlen(expr);
  Vector *tokens = tokenize(expr, expr_len);
  Vector *code = parser(tokens);

  vec_pushi(code, OpPrint);
  print_Opcodes(code);
  printf("%s = ", expr);
  run(code);

  VecForeachWithType(tokens, Token*, token, { free_Token(token); });
  free_vec(tokens);
  free_vec(code);
}

int main(int argc, char const* argv[]) {
  const char* expr = "1 + 1 * 5 * ((2 * 3 - 1) + 3) / 4 - 2";
  calc_expr(expr);

  return 0;
}

expr_calc.rs

#![feature(box_patterns, box_syntax)]
#![allow(dead_code)]
#![allow(non_snake_case)]

mod CalcVM {
    #[derive(Debug, Copy, Clone)]
    pub enum OpCode {
        Push(i32),
        Pop,
        Add,
        Sub,
        Mul,
        Div,
        Mod,
        Print,
        Dup,
    }

    use std::fmt;
    impl fmt::Display for OpCode {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            match self {
                OpCode::Push(v) => write!(f, "Push<{}>", v),
                OpCode::Pop => write!(f, "Pop"),
                OpCode::Add => write!(f, "Add"),
                OpCode::Sub => write!(f, "Sub"),
                OpCode::Mul => write!(f, "Mul"),
                OpCode::Div => write!(f, "Div"),
                OpCode::Mod => write!(f, "Mod"),
                OpCode::Print => write!(f, "Print"),
                OpCode::Dup => write!(f, "Dup"),
            }
        }
    }

    pub fn print_opcodes(code: &[OpCode]) {
        for (idx, op) in code.iter().enumerate() {
            println!("[{}] {}", idx, op);
        }
    }

    pub fn exec(code: &[OpCode]) -> Option<i32> {
        let mut stack = vec![];

        for op in code {
            match op {
                OpCode::Push(val) => {
                    stack.push(*val);
                }
                OpCode::Pop => {
                    stack.pop();
                }
                OpCode::Add => {
                    let (r, l) = (stack.pop().unwrap(), stack.pop().unwrap());
                    stack.push(l + r);
                }
                OpCode::Sub => {
                    let (r, l) = (stack.pop().unwrap(), stack.pop().unwrap());
                    stack.push(l - r);
                }
                OpCode::Mul => {
                    let (r, l) = (stack.pop().unwrap(), stack.pop().unwrap());
                    stack.push(l * r);
                }
                OpCode::Div => {
                    let (r, l) = (stack.pop().unwrap(), stack.pop().unwrap());
                    stack.push(l / r);
                }
                OpCode::Mod => {
                    let (r, l) = (stack.pop().unwrap(), stack.pop().unwrap());
                    stack.push(l % r);
                }
                OpCode::Print => {
                    let val = stack.pop().unwrap();
                    println!("{}", val);
                }
                OpCode::Dup => {
                    let val = *stack.last().unwrap();
                    stack.push(val);
                }
            }
        }

        stack.pop()
    }
}

mod CalcToken {
    #[derive(Debug, Copy, Clone)]
    pub enum Token {
        IntToken(i32),
        AddToken,
        SubToken,
        MulToken,
        DivToken,
        ModToken,
        LparenToken,
        RparenToken,
        WhiteSpaceToken,
        UnkwonToken,
    }

    impl Token {
        pub fn from_char(c: &char) -> Token {
            match c {
                '+' => Token::AddToken,
                '-' => Token::SubToken,
                '*' => Token::MulToken,
                '/' => Token::DivToken,
                '%' => Token::ModToken,
                ' ' => Token::WhiteSpaceToken,
                '(' => Token::LparenToken,
                ')' => Token::RparenToken,
                x if '0' <= *x && *x <= '9' => Token::IntToken(x.to_digit(10).unwrap() as i32),
                _ => Token::UnkwonToken,
            }
        }
    }

    impl std::string::ToString for Token {
        fn to_string(&self) -> String {
            match self {
                Token::IntToken(val) => format!("IntToken<{}>", val),
                Token::AddToken => "AddToken".to_string(),
                Token::SubToken => "SubToken".to_string(),
                Token::MulToken => "MulToken".to_string(),
                Token::DivToken => "DivToken".to_string(),
                Token::ModToken => "ModToken".to_string(),
                Token::LparenToken => "LparenToken".to_string(),
                Token::RparenToken => "RparenToken".to_string(),
                Token::WhiteSpaceToken => "WhiteSpaceToken".to_string(),
                Token::UnkwonToken => "UnkwonToken".to_string(),
            }
        }
    }

    pub fn tokenize(expr: &str) -> Vec<Token> {
        let mut tokens = vec![];
        let mut itr = expr.chars().peekable();
        while let Some(ch) = itr.next() {
            let token = Token::from_char(&ch);
            match token {
                Token::IntToken(val) => {
                    // read number
                    let mut val = val;
                    while let Some(next_ch) = itr.peek() {
                        match Token::from_char(&next_ch) {
                            Token::IntToken(d) => {
                                itr.next(); // consume
                                val = val * 10 + d;
                            }
                            _ => {
                                break;
                            }
                        }
                    }
                    tokens.push(Token::IntToken(val));
                }
                Token::AddToken
                | Token::SubToken
                | Token::MulToken
                | Token::DivToken
                | Token::ModToken
                | Token::LparenToken
                | Token::RparenToken => tokens.push(token),
                Token::WhiteSpaceToken | Token::UnkwonToken => {}
            }
        }
        tokens
    }
}

mod CalcAST {
    use crate::CalcToken::Token;

    fn get_op_pos(tokens: &[Token]) -> Option<usize> {
        let mut pos = None;
        let mut current_priority = std::i32::MAX;
        let mut paren_depth = 0;

        for (i, token) in tokens.iter().enumerate() {
            let priority;
            match token {
                Token::AddToken => priority = 2,
                Token::SubToken => priority = 2,
                Token::MulToken => priority = 3,
                Token::DivToken => priority = 3,
                Token::ModToken => priority = 3,
                Token::LparenToken => {
                    paren_depth += 1;
                    continue;
                }
                Token::RparenToken => {
                    paren_depth -= 1;
                    continue;
                }
                _ => {
                    continue;
                }
            }

            if paren_depth == 0 && priority <= current_priority {
                current_priority = priority;
                pos = Some(i);
            }
        }
        pos
    }

    fn remove_most_outer_paren_token(tokens: &[Token]) -> &[Token] {
        match (tokens.first(), tokens.last()) {
            (Some(Token::LparenToken), Some(Token::RparenToken)) => &tokens[1..tokens.len() - 1],
            _ => tokens,
        }
    }

    #[derive(Debug, Clone, PartialEq)]
    pub enum AST {
        IntNode(i32),
        AddNode(Box<AST>, Box<AST>),
        SubNode(Box<AST>, Box<AST>),
        MulNode(Box<AST>, Box<AST>),
        DivNode(Box<AST>, Box<AST>),
        ModNode(Box<AST>, Box<AST>),
    }

    impl AST {
        pub fn from_tokens(tokens: &[Token]) -> Box<Self> {
            let tokens = remove_most_outer_paren_token(&tokens);

            if let Some(op_pos) = get_op_pos(&tokens) {
                let op_token = tokens[op_pos];
                let lhs_tokens = &tokens[0..op_pos];
                let rhs_tokens = &tokens[op_pos + 1..tokens.len()];

                box match op_token {
                    Token::AddToken => {
                        Self::AddNode(Self::from_tokens(lhs_tokens), Self::from_tokens(rhs_tokens))
                    }
                    Token::SubToken => {
                        Self::SubNode(Self::from_tokens(lhs_tokens), Self::from_tokens(rhs_tokens))
                    }
                    Token::MulToken => {
                        Self::MulNode(Self::from_tokens(lhs_tokens), Self::from_tokens(rhs_tokens))
                    }
                    Token::DivToken => {
                        Self::DivNode(Self::from_tokens(lhs_tokens), Self::from_tokens(rhs_tokens))
                    }
                    Token::ModToken => {
                        Self::ModNode(Self::from_tokens(lhs_tokens), Self::from_tokens(rhs_tokens))
                    }
                    _ => panic!("Unsupported op given"),
                }
            } else if let Token::IntToken(val) = tokens[0] {
                box Self::IntNode(val)
            } else {
                panic!("Unexpected error")
            }
        }
    }

    pub trait ASTOptimizePath {
        fn apply_to(&self, ast: Box<AST>) -> Box<AST>;
    }

    pub struct StrengthReduction;

    impl ASTOptimizePath for StrengthReduction {
        fn apply_to(&self, ast: Box<AST>) -> Box<AST> {
            let apply = |ast| Self.apply_to(ast);
            match *ast {
                AST::IntNode(_) => ast,
                AST::AddNode(lhs, rhs) => match (apply(lhs), apply(rhs)) {
                    (box AST::IntNode(0), rhs) => rhs,
                    (lhs, box AST::IntNode(0)) => lhs,
                    (lhs, rhs) => box AST::AddNode(lhs, rhs),
                },
                AST::SubNode(lhs, rhs) => box AST::SubNode(apply(lhs), apply(rhs)),
                AST::MulNode(lhs, rhs) => match (apply(lhs), apply(rhs)) {
                    (box AST::IntNode(1), rhs) => rhs,
                    (lhs, box AST::IntNode(1)) => lhs,
                    (box AST::IntNode(0), _) => box AST::IntNode(0),
                    (_, box AST::IntNode(0)) => box AST::IntNode(0),
                    (lhs, rhs) => box AST::MulNode(lhs, rhs),
                },
                AST::DivNode(lhs, rhs) => box AST::DivNode(apply(lhs), apply(rhs)),
                AST::ModNode(lhs, rhs) => box AST::ModNode(apply(lhs), apply(rhs)),
            }
        }
    }

    struct IDPath;

    impl ASTOptimizePath for IDPath {
        fn apply_to(&self, ast: Box<AST>) -> Box<AST> {
            ast
        }
    }

    pub struct ASTOptimizePathManager {
        pathes: Vec<Box<dyn ASTOptimizePath>>,
    }

    impl ASTOptimizePathManager {
        pub fn new() -> Self {
            Self { pathes: vec![] }
        }

        pub fn add_path(&mut self, path: Box<dyn ASTOptimizePath>) {
            self.pathes.push(path);
        }

        pub fn apply_pathes(&self, ast: Box<AST>) -> Box<AST> {
            let mut ast = ast;
            for path in self.pathes.iter() {
                ast = path.apply_to(ast);
            }
            ast
        }
    }

    #[macro_export]
    macro_rules! apply_path {
        ( $t:tt , $ast:expr ) => {{
            $t::apply_to(&($t), $ast)
        }};
    }
}

mod CalcCompiler {
    use crate::{CalcAST::AST, CalcVM::OpCode};
    pub fn compile(ast: Box<AST>) -> Vec<OpCode> {
        let mut ret = vec![];
        match *ast {
            AST::IntNode(val) => {
                ret.push(OpCode::Push(val));
            }
            AST::AddNode(lhs, rhs) => {
                ret.append(&mut compile(lhs));
                ret.append(&mut compile(rhs));
                ret.push(OpCode::Add);
            }
            AST::SubNode(lhs, rhs) => {
                ret.append(&mut compile(lhs));
                ret.append(&mut compile(rhs));
                ret.push(OpCode::Sub);
            }
            AST::MulNode(lhs, rhs) => {
                ret.append(&mut compile(lhs));
                ret.append(&mut compile(rhs));
                ret.push(OpCode::Mul);
            }
            AST::DivNode(lhs, rhs) => {
                ret.append(&mut compile(lhs));
                ret.append(&mut compile(rhs));
                ret.push(OpCode::Div);
            }
            AST::ModNode(lhs, rhs) => {
                ret.append(&mut compile(lhs));
                ret.append(&mut compile(rhs));
                ret.push(OpCode::Mod);
            }
        }
        ret
    }
}

pub mod Calculator {
    use crate::{CalcAST, CalcCompiler, CalcToken, CalcVM};

    fn parse(expr: &str) -> Box<CalcAST::AST> {
        let tokens = CalcToken::tokenize(&expr);
        CalcAST::AST::from_tokens(&tokens)
    }

    pub fn calc_expr(expr: &str, pm: Option<&CalcAST::ASTOptimizePathManager>) {
        let ast = {
            let ast = parse(&expr);
            match pm {
                Some(pm) => pm.apply_pathes(ast),
                None => ast,
            }
        };
        let mut code = CalcCompiler::compile(ast);
        code.push(CalcVM::OpCode::Print);
        CalcVM::print_opcodes(&code);
        CalcVM::exec(&code);
    }
}

fn main() {
    let expr = "1 + 1 * 5 * ((2 * 3 - 1) + 3) / 4 - 2 - 1 * 3 / (4 + 2) + 1".to_string();
    let pm = {
        let mut pm = CalcAST::ASTOptimizePathManager::new();
        pm.add_path(Box::new(CalcAST::StrengthReduction));
        pm
    };
    println!("expr: {:?}", expr);
    Calculator::calc_expr(&expr, Some(&pm));

    let test_cases = vec![
        (
            expr.as_str(),
            CalcAST::AST::from_tokens(&CalcToken::tokenize(&expr)),
            10,
        ),
        (
            "1 * 0",
            box CalcAST::AST::MulNode(box CalcAST::AST::IntNode(1), box CalcAST::AST::IntNode(0)),
            0,
        ),
        (
            "1 + 2 * 0",
            box CalcAST::AST::AddNode(
                box CalcAST::AST::IntNode(1),
                box CalcAST::AST::MulNode(
                    box CalcAST::AST::IntNode(2),
                    box CalcAST::AST::IntNode(0),
                ),
            ),
            1,
        ),
        (
            "2 * 0 + 1",
            box CalcAST::AST::AddNode(
                box CalcAST::AST::MulNode(
                    box CalcAST::AST::IntNode(2),
                    box CalcAST::AST::IntNode(0),
                ),
                box CalcAST::AST::IntNode(1),
            ),
            1,
        ),
        (
            "2 * 0 * 1 + 100 * 2",
            box CalcAST::AST::AddNode(
                box CalcAST::AST::MulNode(
                    box CalcAST::AST::MulNode(
                        box CalcAST::AST::IntNode(2),
                        box CalcAST::AST::IntNode(0),
                    ),
                    box CalcAST::AST::IntNode(1),
                ),
                box CalcAST::AST::MulNode(
                    box CalcAST::AST::IntNode(100),
                    box CalcAST::AST::IntNode(2),
                ),
            ),
            200,
        ),
        (
            "2 * 0 * 1 + 100 * 2 + 0 * 3 - 4",
            box CalcAST::AST::SubNode(
                box CalcAST::AST::AddNode(
                    box CalcAST::AST::AddNode(
                        box CalcAST::AST::MulNode(
                            box CalcAST::AST::MulNode(
                                box CalcAST::AST::IntNode(2),
                                box CalcAST::AST::IntNode(0),
                            ),
                            box CalcAST::AST::IntNode(1),
                        ),
                        box CalcAST::AST::MulNode(
                            box CalcAST::AST::IntNode(100),
                            box CalcAST::AST::IntNode(2),
                        ),
                    ),
                    box CalcAST::AST::MulNode(
                        box CalcAST::AST::IntNode(0),
                        box CalcAST::AST::IntNode(3),
                    ),
                ),
                box CalcAST::AST::IntNode(4),
            ),
            196,
        ),
    ];

    for (expr, expected_ast, expected_val) in test_cases {
        println!("---------------------------------");
        println!("expr: {:?}", expr);
        let tokens = CalcToken::tokenize(&expr);
        let ast = CalcAST::AST::from_tokens(&tokens);
        println!("ast<original>: {:?}", ast);
        println!("ast<expected>: {:?}", expected_ast);
        assert!(ast == expected_ast);
        let ast = pm.apply_pathes(ast);
        println!("ast<optimized>: {:?}", ast);
        let mut code = CalcCompiler::compile(ast);

        code.push(CalcVM::OpCode::Dup);
        code.push(CalcVM::OpCode::Print);

        if let Some(val) = CalcVM::exec(&code) {
            println!("val: {}, expected_val: {}", val, expected_val);
            assert!(val == expected_val);
        }
    }
}