APL Lives! (UVa Live Archive World Finals Harbin 2010)
問題
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); } }