APL Lives! (UVa Live Archive World Finals Harbin 2010)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44&page=show_problem&problem=2786

問題

APLのインタプリタを作れ。式は全て右から評価すること。
(例えば - / 1 2 3 は (1 - (2 - 3))=2という意味)
invalidな入力は存在しない。

解法

やるだけ。全て1つのスペース区切りになっているんで1行読み込んで、stringstreamで分割して、後ろから再帰下降構文解析をすれば良い。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <sstream>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

enum OP {
  NOP,
  EQUAL,
  PLUS,
  MINUS,
  MUL,
  SLASH,
  IOTA,
  RHO,
  DROP,
};

typedef vector<int> Array;
typedef vector<Array> Matrix;
typedef vector<Matrix> Tensor;
struct Vect {
  int dimension;
  Tensor vect;
};

void PrintVect(const Vect &v) {
  const Tensor &vect = v.vect;
  REP(z, vect.size()) {
    if (z != 0) { puts(""); }
    REP(y, vect[z].size()) {
      REP(x, vect[z][y].size()) {
        if (x != 0) { putchar(' '); }
        printf("%d", vect[z][y][x]);
      }
      puts("");
    }
  }
}

int n;
char str[1000];
string strs[100];

int Split() {
  n = 0;
  stringstream sin(str);
  while (sin >> strs[n]) { n++; }
  return n;
}


int pos;
map<string, Vect> vars;

//================================================
Vect Plus(Vect lhs, Vect rhs) {
  if (lhs.dimension == 1 && lhs.vect[0][0].size() == 1) {
    swap(lhs, rhs);
  }
  Vect ret = lhs;
  if (rhs.dimension == 1 && rhs.vect[0][0].size() == 1) {
    int v = rhs.vect[0][0][0];
    REP(z, lhs.vect.size()) REP(y, lhs.vect[0].size()) REP(x, lhs.vect[0][0].size()) {
      lhs.vect[z][y][x] += v;
    }
  } else {
    assert(lhs.vect.size() == rhs.vect.size());
    assert(lhs.vect[0].size() == rhs.vect[0].size());
    assert(lhs.vect[0][0].size() == rhs.vect[0][0].size());
    REP(z, lhs.vect.size()) REP(y, lhs.vect[0].size()) REP(x, lhs.vect[0][0].size()) {
      lhs.vect[z][y][x] += rhs.vect[z][y][x];
    }
  }
  return lhs;
}

Vect Mul(Vect lhs, Vect rhs) {
  if (lhs.dimension == 1 && lhs.vect[0][0].size() == 1) {
    swap(lhs, rhs);
  }
  Vect ret = lhs;
  if (rhs.dimension == 1 && rhs.vect[0][0].size() == 1) {
    int v = rhs.vect[0][0][0];
    REP(z, lhs.vect.size()) REP(y, lhs.vect[0].size()) REP(x, lhs.vect[0][0].size()) {
      lhs.vect[z][y][x] *= v;
    }
  } else {
    assert(lhs.vect.size() == rhs.vect.size());
    assert(lhs.vect[0].size() == rhs.vect[0].size());
    assert(lhs.vect[0][0].size() == rhs.vect[0][0].size());
    REP(z, lhs.vect.size()) REP(y, lhs.vect[0].size()) REP(x, lhs.vect[0][0].size()) {
      lhs.vect[z][y][x] *= rhs.vect[z][y][x];
    }
  }
  return lhs;
}

Vect Minus(Vect lhs, Vect rhs) {
  Vect minus;
  minus.dimension = 1;
  minus.vect = Tensor(1, Matrix(1, Array(1, -1)));
  rhs = Mul(rhs, minus);
  return Plus(lhs, rhs);
}

Vect SlashPlus(Vect rhs) {
  int d = rhs.dimension;
  REP(z, rhs.vect.size()) {
    REP(y, rhs.vect[0].size()) {
      for (int x = rhs.vect[0][0].size() - 2; x >= 0; x--) {
        rhs.vect[z][y][x] += rhs.vect[z][y][x + 1];
      }
    }
  }
  Vect ret;
  ret.dimension = max(d - 1, 1);
  ret.vect = Tensor(1, Matrix(rhs.vect.size(), Array(rhs.vect[0].size())));
  REP(z, rhs.vect.size()) REP(y, rhs.vect[0].size()) {
    ret.vect[0][z][y] = rhs.vect[z][y][0];
  }
  return ret;
}

Vect SlashMinus(Vect rhs) {
  int d = rhs.dimension;
  REP(z, rhs.vect.size()) {
    REP(y, rhs.vect[0].size()) {
      for (int x = rhs.vect[0][0].size() - 2; x >= 0; x--) {
        rhs.vect[z][y][x] -= rhs.vect[z][y][x + 1];
      }
    }
  }
  Vect ret;
  ret.dimension = max(d - 1, 1);
  ret.vect = Tensor(1, Matrix(rhs.vect.size(), Array(rhs.vect[0].size())));
  REP(z, rhs.vect.size()) REP(y, rhs.vect[0].size()) {
    ret.vect[0][z][y] = rhs.vect[z][y][0];
  }
  return ret;
}

Vect SlashMul(Vect rhs) {
  int d = rhs.dimension;
  REP(z, rhs.vect.size()) {
    REP(y, rhs.vect[0].size()) {
      for (int x = rhs.vect[0][0].size() - 2; x >= 0; x--) {
        rhs.vect[z][y][x] *= rhs.vect[z][y][x + 1];
      }
    }
  }
  Vect ret;
  ret.dimension = max(d - 1, 1);
  ret.vect = Tensor(1, Matrix(rhs.vect.size(), Array(rhs.vect[0].size())));
  REP(z, rhs.vect.size()) REP(y, rhs.vect[0].size()) {
    ret.vect[0][z][y] = rhs.vect[z][y][0];
  }
  return ret;
}



Vect Iota(Vect rhs) {
  assert(rhs.dimension == 1 && rhs.vect[0][0].size() == 1);
  int s = rhs.vect[0][0][0];
  assert(s >= 0);
  Vect ret;
  ret.dimension = 1;
  ret.vect = Tensor(1, Matrix(1, Array(s)));
  REP(i, s) { ret.vect[0][0][i] = i + 1; }
  return ret;
}

Vect Rho(Vect lhs, Vect rhs) {
  assert(lhs.dimension == 1 && lhs.vect[0][0].size() <= 3);
  Vect ret;
  ret.dimension = lhs.vect[0][0].size();
  int FZ = rhs.vect.size();
  int FY = rhs.vect[0].size();
  int FX = rhs.vect[0][0].size();
  int fz = 0;
  int fy = 0;
  int fx = 0;
  int TZ = 1;
  int TY = 1;
  int TX = 1;
  if (ret.dimension >= 3) { TZ = lhs.vect[0][0][ret.dimension - 3]; }
  if (ret.dimension >= 2) { TY = lhs.vect[0][0][ret.dimension - 2]; }
  if (ret.dimension >= 1) { TX = lhs.vect[0][0][ret.dimension - 1]; }
  int tz = 0;
  int ty = 0;
  int tx = 0;
  ret.vect = Tensor(TZ, Matrix(TY, Array(TX)));
  while (tz < TZ) {
    ret.vect[tz][ty][tx] = rhs.vect[fz][fy][fx];
    fx++;
    if (fx == FX) { fx = 0; fy++; }
    if (fy == FY) { fy = 0; fz++; }
    if (fz == FZ) { fz = 0; }

    tx++;
    if (tx == TX) { tx = 0; ty++; }
    if (ty == TY) { ty = 0; tz++; }
  }
  return ret;
}

Vect Drop(Vect lhs, Vect rhs) {
  assert(lhs.dimension == 1 && lhs.vect[0][0].size() == 1);
  int s = lhs.vect[0][0][0];
  assert(s >= 0);
  assert(rhs.dimension == 1);
  assert((int)rhs.vect[0][0].size() > s);
  rhs.vect[0][0].erase(rhs.vect[0][0].begin(), rhs.vect[0][0].begin() + s);
  return rhs;
}


//=========================================
Vect GetEqu();
Vect GetNumVect() {
  Vect ret;
  ret.dimension = 1;
  ret.vect = Tensor(1, Matrix(1, Array(0)));
  while (pos >= 0 && isdigit(strs[pos][0])) {
    ret.vect[0][0].push_back(atoi(strs[pos].c_str()));
    pos--;
  }
  reverse(ret.vect[0][0].begin(), ret.vect[0][0].end());
  return ret;
}

int GetOp() {
  if (pos == -1 || strs[pos] == "(" || isdigit(strs[pos][0])) { return NOP; }
  string s = strs[pos];
  pos--;
  if (s == "=") { return EQUAL; }
  if (s == "+") { return PLUS; }
  if (s == "-") { return MINUS; }
  if (s == "*") { return MUL; }
  if (s == "/") { return SLASH; }
  if (s == "iota") { return IOTA; }
  if (s == "rho") { return RHO; }
  if (s == "drop") { return DROP; }
  assert(false);
  return NOP;
}

Vect GetVect() {
  Vect rhs;
  if (strs[pos] == ")") {
    pos--;
    rhs = GetEqu();
    assert(strs[pos] == "(");
    pos--;
  } else if (isalpha(strs[pos][0])) {
    assert(vars.count(strs[pos]));
    rhs = vars[strs[pos]];
    pos--;
  } else if (isdigit(strs[pos][0])) {
    rhs = GetNumVect();
  } else {
    assert(false);
  }
  return rhs;
}


Vect GetEqu() {
  Vect rhs = GetVect();
  while (pos != -1 && strs[pos] != "(") {
    int op = GetOp();
    assert(op != NOP);
    if (op == EQUAL) {
      assert(isalpha(strs[pos][0]));
      vars[strs[pos]] = rhs;
      pos--;
    } else if (op == PLUS) {
      Vect lhs = GetVect();
      rhs = Plus(lhs, rhs);
    } else if (op == MINUS) {
      Vect lhs = GetVect();
      rhs = Minus(lhs, rhs);
    } else if (op == MUL) {
      Vect lhs = GetVect();
      rhs = Mul(lhs, rhs);
    } else if (op == SLASH) {
      int op2 = GetOp();
      if (op2 == PLUS) {
        rhs = SlashPlus(rhs);
      } else if (op2 == MINUS) {
        rhs = SlashMinus(rhs);
      }  else if (op2 == MUL) {
        rhs = SlashMul(rhs);
      }
    } else if (op == IOTA) {
      rhs = Iota(rhs);
    } else if (op == RHO) {
      Vect lhs = GetVect();
      rhs = Rho(lhs, rhs);
    } else if (op == DROP) {
      Vect lhs = GetVect();
      rhs = Drop(lhs, rhs);
    } else {
      assert(false);
    }
  }
  return rhs;
}

int main() {
  int test_case = 0;
  while (gets(str), str[0] != '#') {
    test_case++;
    pos = Split() - 1;
    //REP(i, n) { cout << strs[i] << endl; }
    Vect vect = GetEqu();
    printf("Case %d: %s\n", test_case, str);
    PrintVect(vect);
  }
}