#include #include #include #include #include #include #include #include #include using namespace std; ifstream fin("equation.txt"); #define cin fin struct state { bool lhs_filled; int lhs, rhs; string s_lhs, str; int cursor; int count_num; state() : str(128, ' ') { lhs_filled = false; lhs = rhs = 0; cursor = count_num = 0; } }; enum TokenType { T_VALUE = 0, T_PLUS, T_MINUS, T_TIMES, T_LPAREN, T_RPAREN, T_EOL }; struct Token { TokenType type; int value; Token(TokenType type) : type(type), value(0) {} Token(int value) : type(T_VALUE), value(value) {} }; class Tokenizer { private: string str; int cur; public: Tokenizer(const string& str) : str(str), cur(0) {} Token _read() { while(cur < str.size() && str[cur] == ' ') cur++; if(cur >= str.size()) return Token(T_EOL); if(isdigit(str[cur])) { const char *p = str.c_str() + cur, *q; int v = strtol(p, (char **) &q, 10); cur += q - p; return Token(v); } else switch(str[cur++]) { case '+': return Token(T_PLUS); case '-': return Token(T_MINUS); case '*': return Token(T_TIMES); case '(': return Token(T_LPAREN); case ')': return Token(T_RPAREN); default : assert(false); } assert(false); return Token(T_EOL); } Token read() { const Token result = _read(); //cout << "Tok(" << result.type << ", " << result.value << ")" << endl; return result; } }; #define DEF_(name) int name(Token& la, Tokenizer& tok) #define NEXT() la = tok.read() DEF_(E); DEF_(F) { switch(la.type) { case T_VALUE: { int v = la.value; NEXT(); return v; } case T_LPAREN: { NEXT(); int v = E(la, tok); throw "ERROR Fparen"; NEXT(); return v; } default: throw "ERROR Ferror"; } } DEF_(T) { int v1 = F(la, tok); while(la.type == T_TIMES) { NEXT(); int v2 = F(la, tok); v1 *= v2; } if(la.type != T_EOL && la.type != T_PLUS && la.type != T_MINUS && la.type != T_RPAREN) throw "ERROR T"; return v1; } DEF_(E) { int v1 = T(la, tok); while(1) { if(la.type == T_PLUS) { NEXT(); int v2 = T(la, tok); v1 += v2; } else if(la.type == T_MINUS) { NEXT(); int v2 = T(la, tok); v1 -= v2; } else break; } if(la.type != T_EOL && la.type != T_RPAREN) throw "ERROR E"; return v1; } bool parse(const string& str, int& result) { try { //cout << "Try to parse " << str << endl; Tokenizer tok(str); Token la = tok.read(); result = E(la, tok); return true; } catch(const char *err) { cerr << err << endl; return false; } } void dfs(int y, int x, state st, vector >& visited, const vector >& matr, set& result) { //cout << "(" << x << "," << y << ")" << endl; char c, p = st.cursor ? st.str[st.cursor - 1] : ' '; switch(c = matr[y][x]) { case '=': if(st.lhs_filled) return; if(! st.count_num) return; if(st.lhs_filled = parse(st.str, st.lhs)) { st.s_lhs = st.str; st.str.clear(); st.str.resize(128, ' '); st.cursor = st.count_num = 0; } break; case '0': if(p == '+' || p == '-' || p == '*') return; case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': if(++st.count_num >= 5) return; if(p == '(' || p == ')') return; st.str[st.cursor++] = c; break; case '+': case '-': case '*': case '(': case ')': if(! st.count_num) return; st.count_num = 0; st.str[st.cursor++] = c; break; } visited[y][x] = true; if(y == matr.size() - 1) { int v; if(parse(st.str, v) && st.lhs == v) { unsigned pos = st.s_lhs.find_last_not_of(' '); assert(pos != string::npos); string str = st.s_lhs.substr(0, pos + 1) + '='; pos = st.str.find_last_not_of(' '); assert(pos != string::npos); result.insert(str + st.str.substr(0, pos + 1)); } } if(y > 0 && !visited[y - 1][x]) dfs(y - 1, x, st, visited, matr, result); if(y < matr.size() - 1 && !visited[y + 1][x]) dfs(y + 1, x, st, visited, matr, result); if(x > 0 && ! visited[y][x - 1]) dfs(y, x - 1, st, visited, matr, result); if(x < matr[0].size() - 1 && ! visited[y][x + 1]) dfs(y, x + 1, st, visited, matr, result); visited[y][x] = false; } void solve(const vector >& m) { vector > visited(m.size(), vector(m[0].size())); set s; for(int i = 0; i < m[0].size(); i++) dfs(0, i, state(), visited, m, s); for(set::const_iterator it = s.begin(); it != s.end(); ++it) cout << *it << endl; } int main() { if(!fin) return -1; int h, w; int ncase = 0; while(cin >> h >> w, h || w) { vector > matr(h, vector(w)); cout << "Table " << ++ncase << endl; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) cin >> matr[i][j]; solve(matr); cout << endl; } return 0; }