UVaOJ 1596 - Bug Hunt

问题描述

解法一：模拟 + 注意 IO 格式

分析题意，我们需要实现如下功能：

给定一个表达式如 a[b[0]], 能够解析 parse 出一层子表达式 b[0], 方便后续递归处理；
给定一个完整表达式，递归进行评估 evalute 看是否能成功得到对应值；
- 对于带 [] 表达式的解析，显然用栈模拟比较方便；
判断一个表达式是赋值表达式还是声明表达式 ——
- 对于声明式表达式，用一个 map<string, int> 模拟记录容量，即下标范围；
- 对于赋值表达式，先对右值进行评估，再看左值下标是否合法，最后赋值；
- 用 map<string, map<int, int>> 模拟一个二维数组进行存储，会比较方便。

注意这题对结束单个 case 输入与整个输入的判断方法（参考代码和注释）。

#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;
}

#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;

}

} // End of one line

if (!end_of_input) cout << (find_bug ? num_bugline : 0) << endl;

} // End of input

return 0;

}

#TODO

#TODO

AOAPC II UVaOJ