题目分析

我们需要模拟一个简单的电子表格，其中包含9行（1-9）和26列（A-Z）。每个单元格可以包含一个表达式，表达式可能包含：

• 整数常量（如 $567$）
• 单元格引用（如 $B1$）
• 运算符（$+$, $-$, $*$, $/$，其中 $/$ 是整除）
• 括号（用于改变运算优先级）

特殊规则：

1. 如果表达式引用的单元格未定义，其值默认为 $0$。
2. 如果发生 循环引用（如 $A1=B1$, $B1=A1$），则无法计算，输出 $1000000$。
3. 除零运算 的结果为 $0$。

解题思路

1. 输入处理

   • 读取 $N$ 个表达式，存储为 unordered_map<string, string>，键是单元格名称（如 "A1"），值是其表达式（如 "B1+C5"）。
   • 注意去除表达式前后的空格。

2. 表达式求值

   • 使用 递归下降解析 或 逆波兰表达式（RPN） 来计算表达式的值。
   • 遇到 单元格引用 时，递归计算其值，并检测 循环引用（用 visiting 集合记录当前正在计算的单元格）。
   • 使用 记忆化存储（memoization） 避免重复计算。

3. 错误处理

   • 如果检测到循环引用，直接抛出异常，并在 main 中捕获，输出 $1000000$。

代码实现

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <stack>
#include <cctype>
#include <stdexcept>

using namespace std;

unordered_map<string, string> expressions;
unordered_map<string, int> memo;
unordered_set<string> visiting;

bool is_cell_reference(const string& token) {
   if (token.size() < 2) return false;
   if (!isalpha(token[0])) return false;
   if (token[1] < '1' || token[1] > '9') return false;
   for (size_t i = 2; i < token.size(); i++) {
       if (!isdigit(token[i])) return false;
   }
   return true;
}

int evaluate_cell(const string& cell);

vector<string> tokenize(const string& expr) {
   vector<string> tokens;
   string current;
   for (char c : expr) {
       if (isspace(c)) continue;
       if (isalnum(c) || c == '.') {
           current += c;
       } else {
           if (!current.empty()) {
               tokens.push_back(current);
               current.clear();
           }
           if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') {
               tokens.push_back(string(1, c));
           }
       }
   }
   if (!current.empty()) {
       tokens.push_back(current);
   }
   return tokens;
}

int evaluate_expression(const string& expr) {
   vector<string> tokens = tokenize(expr);
   vector<string> output;
   stack<string> ops;
   unordered_map<string, int> precedence = {
       {"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}
   };

   for (const string& token : tokens) {
       if (isdigit(token[0]) || is_cell_reference(token)) {
           output.push_back(token);
       } else if (token == "(") {
           ops.push(token);
       } else if (token == ")") {
           while (!ops.empty() && ops.top() != "(") {
               output.push_back(ops.top());
               ops.pop();
           }
           ops.pop(); // Remove "("
       } else { // operator
           while (!ops.empty() && ops.top() != "(" && 
                  precedence[ops.top()] >= precedence[token]) {
               output.push_back(ops.top());
               ops.pop();
           }
           ops.push(token);
       }
   }
   while (!ops.empty()) {
       output.push_back(ops.top());
       ops.pop();
   }

   stack<int> nums;
   for (const string& token : output) {
       if (isdigit(token[0])) {
           nums.push(stoi(token));
       } else if (is_cell_reference(token)) {
           nums.push(evaluate_cell(token));
       } else {
           int b = nums.top(); nums.pop();
           int a = nums.top(); nums.pop();
           if (token == "+") nums.push(a + b);
           else if (token == "-") nums.push(a - b);
           else if (token == "*") nums.push(a * b);
           else if (token == "/") nums.push(b == 0 ? 0 : a / b);
       }
   }
   return nums.top();
}

int evaluate_cell(const string& cell) {
   if (memo.count(cell)) return memo[cell];
   if (!expressions.count(cell)) return 0;
   if (visiting.count(cell)) throw runtime_error("Circular reference");
   
   visiting.insert(cell);
   try {
       int value = evaluate_expression(expressions[cell]);
       memo[cell] = value;
       return value;
   } catch (...) {
       throw;
   }
   visiting.erase(cell);
}

int main() {
   int N;
   cin >> N;
   cin.ignore(); // Skip newline after N
   
   for (int i = 0; i < N; i++) {
       string line;
       getline(cin, line);
       size_t eq_pos = line.find('=');
       if (eq_pos == string::npos) continue;
       string cell = line.substr(0, eq_pos);
       string expr = line.substr(eq_pos + 1);
       // Trim whitespace
       cell.erase(0, cell.find_first_not_of(" \t"));
       cell.erase(cell.find_last_not_of(" \t") + 1);
       expr.erase(0, expr.find_first_not_of(" \t"));
       expr.erase(expr.find_last_not_of(" \t") + 1);
       expressions[cell] = expr;
   }

   try {
       int result = evaluate_cell("A1");
       cout << result << endl;
   } catch (...) {
       cout << 1000000 << endl;
   }

   return 0;
}