MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1596 - Bug Hunt
AOAPC II

UVaOJ 1596 - Bug Hunt

Chai
2021-11-24 0:00:00在线评测阅读 494

问题描述

p1596

原题链接:UVaOJ 1596 - Bug Hunt

相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-9

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

分析题意,我们需要实现如下功能:

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

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

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz