操車場アルゴリズム

shunting_yard.c

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

enum oper { lparens, add, sub, mul, div_op };

int pri(enum oper op) {
  switch (op) {
    case lparens:
      return 0;
    case add:
    case sub:
      return 2;
    case mul:
    case div_op:
      return 3;
  }
}

void skip_spaces(char **s) {
  for (; isspace(**s); ++*s)
    ;
}

int read_num(char **s) {
  int x = 0;
  for (; isdigit(**s); ++*s) {
    x *= 10; x += **s - '0';
  }
  return x;
}

int calc(enum oper op, int x, int y) {
  switch (op) {
    case add:
      return x+y;
    case sub:
      return x-y;
    case mul:
      return x*y;
    case div_op:
      return x/y;
    default:
      printf("calc\n");
      exit(EXIT_FAILURE);
  }
}

void push(int *num_s, int *num_p, enum oper *oper_s, int *oper_p, enum oper op) {
  while (*oper_p >= 1 && *num_p >= 2 && pri(oper_s[*oper_p-1]) >= pri(op)) {
    num_s[*num_p-2] = calc(oper_s[*oper_p-1], num_s[*num_p-2], num_s[*num_p-1]);
    --*num_p; --*oper_p;
  }
  oper_s[*oper_p] = op;
  ++*oper_p;
}

void pop(int *num_s, int *num_p, enum oper *oper_s, int *oper_p) {
  if (*num_p < 2) {
    printf("oper\n");
    exit(EXIT_FAILURE);
  }
  num_s[*num_p-2] = calc(oper_s[--*oper_p], num_s[*num_p-2], num_s[*num_p-1]);
  --*num_p;
}

int main(void) {
  enum oper oper_s[256]; int oper_p = 0;
  int num_s[256]; int num_p = 0;
  char s[] = "10 * 9 + 8 - 7 * 6 / 5 + (4 - 3 * (2 - 1))", *p = s;
  skip_spaces(&p);
  for (int i = p - s; s[i];) {
    switch (s[i]) {
      case '+':
        push(num_s, &num_p, oper_s, &oper_p, add);
        ++i;
        break;
      case '-':
        push(num_s, &num_p, oper_s, &oper_p, sub);
        ++i;
        break;
      case '*':
        push(num_s, &num_p, oper_s, &oper_p, mul);
        ++i;
        break;
      case '/':
        push(num_s, &num_p, oper_s, &oper_p, div_op);
        ++i;
        break;
      case '(':
        oper_s[oper_p++] = lparens;
        ++i;
        break;
      case ')':
        while (oper_s[oper_p-1] != lparens) {
          if (oper_p <= 0) {
            printf("parens\n");
            exit(EXIT_FAILURE);
          }
          pop(num_s, &num_p, oper_s, &oper_p);
        }
        --oper_p;
        ++i;
        break;
      default:
        p = s+i;
        num_s[num_p++] = read_num(&p);
        if (p == s+i) {
          printf("num\n");
          exit(EXIT_FAILURE);
        }
        i = p - s;
        break;
    }
    p = s+i;
    skip_spaces(&p);
    i = p - s;
  }
  while (oper_p) {
    pop(num_s, &num_p, oper_s, &oper_p);
  }
  printf("%d\n", *num_s);
}