厦门大学夏令营机试第二题-堆栈合理性判断

题目描述

给定两个整数 N 和 M，N 代表需要判断的操作个数，M 代表堆栈的容量。接着输入 N 个堆栈的操作，S 代表入栈，X 代表出栈，每行输入一个字符串，判断每次操作是否合法。

例如：

• 如果在栈为空的时候执行出栈操作，则操作不合法。
• 如果栈的大小超过容量 M，则操作不合法。

题解

为了判断堆栈操作的合法性，我们可以使用 C++ 编写一个程序来完成。主要的思路是：

1. 使用一个栈来模拟堆栈操作。
2. 遍历所有操作，根据操作类型进行入栈或出栈，并在每一步检查操作是否合法。

以下是完整的 C++ 代码：

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

bool isValidStackOperations(int M, const string& operations) {
    stack<int> stk;
    for (char op : operations) {
        if (op == 's') {
            if (stk.size() >= M) {
                return false; // 如果栈的大小超过容量 M，则操作不合法
            }
            stk.push(1); // 用1代表任意入栈的数字，因为具体数字不重要
        } else if (op == 'x') {
            if (stk.empty()) {
                return false; // 如果在栈为空的时候执行出栈操作，则操作不合法
            }
            stk.pop();
        } else {
            return false; // 非法字符
        }
    }
    return true; // 所有操作合法
}

int main() {
    int N, M;
    cout << "请输入操作序列的个数N和堆栈容量M: ";
    cin >> N >> M;
    cin.ignore();  // 清除输入缓冲区

    vector<string> allOperations(N);

    for (int i = 0; i < N; ++i) {
        cout << "请输入操作字符串: ";
        getline(cin, allOperations[i]);
    }

    for (string operations : allOperations) {
        if (isValidStackOperations(M, operations)) {
            cout << "操作合法" << endl;
        } else {
            cout << "操作不合法" << endl;
        }
    }

    return 0;
}

示例1

输入：

2 3
ssxxs
sxsxsxssxxsss

输出：

请输入操作序列的个数N和堆栈容量M: 2 3
请输入操作字符串: ssxxs
请输入操作字符串: sxsxsxssxxsss
操作合法
操作不合法