机试题——栈溢出判断

问题背景

在程序运行过程中，函数调用会占用栈空间。如果调用链过长或者某些函数占用的栈空间过大，可能会导致栈溢出。本题的目标是根据给定的函数调用关系和每个函数的栈大小，判断程序是否存在栈溢出的风险。

输入描述

输入包括三个部分：

1. 函数数量：第一行输入一个数字 ( N )，表示有 ( N ) 个函数。
2. 函数栈大小：接下来 ( N ) 行，每行包含一个函数名称和对应的栈大小，用空格隔开。函数名称为单个大写字母。
3. 函数调用关系：接下来一行输入一个数字 ( M )，表示有 ( M ) 行函数调用关系。每行表示一个函数调用链，第一个字母是调用函数，后面的字母是被调用函数，按序调用。
4. 系统最大栈空间：最后一行输入一个数字 ( K )，表示系统配置的最大栈空间。

输出描述

输出包括三个部分：

1. 是否会发生栈溢出。如果发生栈溢出，输出 true；否则输出 false。
2. 如果栈溢出，输出发生栈溢出的调用路径（路径只输出到触发栈溢出的函数）；如果没有栈溢出，输出最大消耗栈的调用路径。
3. 如果栈溢出，输出发生栈溢出时调用关系的栈大小；如果没有栈溢出，输出最大栈消耗。

用例输入

输入：

6
A 20
B 10
C 5
D 15
E 50
F 60
3
A B C
B D
C E F
70

输出：

true A-C-E 75

输入：

6
A 20
B 10
C 5
D 15
E 50
F 60
3
A B C
B D
C E F
100

输出：

false A-C-F 85

解题思路

问题分析

1. 函数调用关系：通过输入的调用关系，可以构建一个有向图，其中节点表示函数，边表示调用关系。
2. 栈空间计算：从主函数开始，递归遍历调用链，计算每条路径的栈空间占用。
3. 判断栈溢出：在递归过程中，如果发现当前路径的栈空间占用超过了系统最大栈空间 ( K )，则发生栈溢出。
4. 记录最大栈路径：即使没有栈溢出，也需要记录最大栈空间占用的路径。

算法设计

1. 构建调用关系图：使用 map<string, vector<string>> 存储每个函数的调用关系。
2. 存储栈大小：使用 map<string, int> 存储每个函数的栈大小。
3. 深度优先搜索（DFS）：
   • 从主函数开始递归遍历调用链。
   • 在递归过程中，维护当前路径的栈空间占用。
   • 如果当前路径的栈空间占用超过系统最大栈空间，记录栈溢出路径和栈大小。
   • 如果没有栈溢出，记录最大栈空间占用的路径。
4. 输出结果：根据是否发生栈溢出，输出相应的结果。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <list>
#include <sstream>
#include <bitset>
#include <stack>
#include <climits>
#include <iomanip>
#include <cstdint>
using namespace std;

map<string, vector<string>> g; // 函数调用关系
map<string, int> fun_st; // 函数和栈大小
int sys_size; // 系统最大栈空间
vector<string> st; // 当前路径
bool flag = true; // 标记是否发生栈溢出
int st_size = 0; // 当前最大栈空间占用
vector<string> st_res; // 最大栈空间占用的路径

// 深度优先搜索
void dfs(const string& root, int cursize) {
    if (flag == false) return; // 如果已经发生栈溢出，直接返回
    if (cursize > sys_size) { // 判断是否栈溢出
        flag = false;
        cout << "true ";
        for (int i = 0; i < st.size(); i++) {
            cout << st[i];
            if (i != st.size() - 1) cout << "-";
        }
        cout << " " << cursize << endl;
        return;
    }
    if (cursize > st_size) { // 更新最大栈空间占用的路径
        st_size = cursize;
        st_res = st;
    }
    for (int i = 0; i < g[root].size(); i++) {
        st.push_back(g[root][i]); // 将当前函数加入路径
        dfs(g[root][i], cursize + fun_st[g[root][i]]); // 递归调用
        st.pop_back(); // 回溯，移除当前函数
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n; // 输入函数数量
    string fun;
    int stsize;
    for (int i = 0; i < n; i++) {
        cin >> fun >> stsize; // 输入每个函数的栈大小
        fun_st[fun] = stsize;
    }

    // 输入函数调用关系
    cin >> n;
    cin.ignore();
    string b = "";
    for (int i = 0; i < n; i++) {
        string input;
        getline(cin, input);
        istringstream is(input);
        string be, ne;
        is >> be;
        if (b.size() == 0) b = be; // 主函数
        while (is >> ne) {
            g[be].push_back(ne); // 构建调用关系
        }
    }

    cin >> sys_size; // 输入系统最大栈空间
    st.push_back(b); // 从主函数开始
    dfs(b, fun_st[b]); // 开始深度优先搜索

    if (flag) { // 如果没有栈溢出
        cout << "false ";
        for (int i = 0; i < st_res.size(); i++) {
            cout << st_res[i];
            if (i != st_res.size() - 1) cout << "-";
        }
        cout << " " << st_size << endl;
    }
    return 0;
}