问题描述
p1596相关说明：本题为《算法竞赛入门经典（第2版）》习题 5-9
解法一：模拟 + 注意 IO 格式
分析题意，我们需要实现如下功能：
- 给定一个表达式如 a[b[0]], 能够解析 parse 出一层子表达式 b[0], 方便后续递归处理；
- 给定一个完整表达式，递归进行评估
evalute 看是否能成功得到对应值；
- 对于带 [] 表达式的解析，显然用栈模拟比较方便；
- 判断一个表达式是赋值表达式还是声明表达式 ——
- 对于声明式表达式，用一个 map<string, int> 模拟记录容量，即下标范围；
- 对于赋值表达式，先对右值进行评估，再看左值下标是否合法，最后赋值；
- 用 map<string, map<int, int>> 模拟一个二维数组进行存储，会比较方便。
注意这题对结束单个 case 输入与整个输入的判断方法（参考代码和注释）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <bits/stdc++.h> using namespace std; using mem = map<string, map<int, int>>; // mem["a"][0] = 1 means a[0] = 1 using len = map<string, int>; // len["a"] = 1 means a's length is 1 pair<string, string> parse(string expression) { // "a[b[0]]" -> ("a", "b[0]") int i = expression.find('['); return {expression.substr(0, i), expression.substr(i + 1, expression.size() - i - 2)}; } int evalute(const string& expression, mem& memory, len& length) { stack<string> variable; string cur = expression; while (!isdigit(cur[0])) { pair<string, string> result = parse(cur); variable.push(result.first); cur = result.second; } int value = stoi(cur); while (!variable.empty()) { cur = variable.top(); if (value >= length[cur] || memory[cur].find(value) == memory[cur].end()) return -1; // Bug! variable.pop(); value = memory[cur][value]; // Get the new idx or the final value } return value; // Evalute susccessfully } int main() { string expression; bool end_of_input = false; while (!end_of_input) { end_of_input = true; bool find_bug = false; int num_bugline = 0; mem memory; len length; while (cin >> expression && expression != ".") { end_of_input = false; if (find_bug) continue; num_bugline++; // Note it stop increase when find bug int pos = expression.find("="); if (pos == string::npos) { // Declare a variable (set length) pair<string, string> result = parse(expression); length[result.first] = stoi(result.second); } else { // Assign a value to a variable string left_exp = expression.substr(0, pos); string right_exp = expression.substr(pos + 1); int value = evalute(right_exp, memory, length); // to be assigned if (value != -1) { // Evalute successfully pair<string, string> ss = parse(left_exp); int idx = evalute(ss.second, memory, length); if (idx != -1 && idx < length[ss.first]) { // Legal index memory[ss.first][idx] = value; } else find_bug = true; } else find_bug = true; } } // End of one line if (!end_of_input) cout << (find_bug ? num_bugline : 0) << endl; } // End of input return 0; } |
|
1 |
#TODO |
