天秀信息学奥赛

天秀信息学奥赛

关注
发信
关注(28)粉丝(399)

信息学奥赛一本通数据结构1 - 栈

1331：【例1-2】后缀表达式的值

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    stack<int> stk;  // 定义一个存储整数的栈
    string exp;      // 存储后缀表达式中的每个元素
    
    // 读入后缀表达式,以@结束
    while (cin >> exp) {
        if (exp == "@") break;  // 读到@时结束输入
        
        if (isdigit(exp[0])) {  // 如果是数字,转换为整数并入栈
            stk.push(stoi(exp));
        } else {  // 如果是运算符,弹出栈顶两个元素进行计算,并将结果入栈
            int num2 = stk.top(); stk.pop();
            int num1 = stk.top(); stk.pop();
            switch (exp[0]) {
                case '+': stk.push(num1 + num2); break;
                case '-': stk.push(num1 - num2); break;
                case '*': stk.push(num1 * num2); break;
                case '/': stk.push(num1 / num2); break;
            }
        }
    }
    
    // 输出结果
    cout << stk.top() << endl;
    
    return 0;
}

1353：表达式括号匹配(stack)

解析:
定义一个函数isMatched,用于判断表达式中的左右圆括号是否匹配。
函数接受一个字符串exp作为参数,表示输入的表达式。
函数返回一个布尔值,表示括号是否匹配。
在isMatched函数中,定义一个栈stk,用于存储左圆括号。
使用for循环遍历表达式的每个字符:
如果当前字符是左圆括号(,将其压入栈中。
如果当前字符是右圆括号),判断栈是否为空或者栈顶元素是否为左圆括号(:
如果栈为空或者栈顶元素不是左圆括号,说明括号不匹配,返回false。
否则,弹出栈顶的左圆括号,表示匹配成功。
循环结束后,判断栈是否为空:
如果栈为空,说明所有的左圆括号都被匹配,返回true。
否则,说明还有未匹配的左圆括号,返回false。
在main函数中,使用getline函数读取一行输入,以@作为分隔符。
调用isMatched函数判断表达式中的括号是否匹配,并输出相应的结果:
如果匹配,输出"YES"。
如果不匹配,输出"NO"。
对于输入样例2*(x+y)/(1-x)@,程序的执行过程如下:

读取表达式2*(x+y)/(1-x)。
调用isMatched函数判断括号是否匹配:
遇到(时,将其压入栈中。
遇到)时,弹出栈顶的(,表示匹配成功。
遍历完表达式后,栈为空,说明所有的括号都匹配成功。
输出"YES"。
对于样例输入2(25+x)*(a*(a+b+b)@,程序的执行过程如下:

读取表达式(25+x)*(a*(a+b+b)。
调用isMatched函数判断括号是否匹配:
遇到(时,将其压入栈中。
遇到)时,弹出栈顶的(,表示匹配成功。
遍历完表达式后,栈中还有一个(,说明有左圆括号未匹配。
输出"NO"。
这个程序的时间复杂度为O(n),其中n为表达式的长度,因为需要遍历表达式的每个字符。空间复杂度为O(n),最坏情况下栈中需要存储所有的左圆括号。

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool isMatched(string exp) {
    stack<char> stk;
    
    for (char ch : exp) {
        if (ch == '(') {
            stk.push(ch);
        } else if (ch == ')') {
            if (stk.empty() || stk.top() != '(') {
                return false;
            }
            stk.pop();
        }
    }
    
    return stk.empty();
}

int main() {
    string exp;
    getline(cin, exp, '@');
    
    if (isMatched(exp)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}

1354：括弧匹配检验

解析:

  1. 首先,我们定义了一个函数isMatched,用于判断表达式中的括号是否匹配。

    • 函数接受一个字符串exp作为参数,表示输入的表达式。
    • 函数返回一个布尔值,表示括号是否匹配。

  2. 在isMatched函数中,我们定义了一个栈stk,用于存储左括号。

  3. 我们使用for循环遍历表达式的每个字符:

    • 如果当前字符是左圆括号(或左方括号[,我们将其压入栈中。
    • 如果当前字符是右圆括号),我们判断栈是否为空或者栈顶元素是否为对应的左圆括号(:
      • 如果栈为空或者栈顶元素不是左圆括号,说明括号不匹配,我们返回false。
      • 否则,我们弹出栈顶的左圆括号,表示匹配成功。
    • 如果当前字符是右方括号],我们判断栈是否为空或者栈顶元素是否为对应的左方括号[:
      • 如果栈为空或者栈顶元素不是左方括号,说明括号不匹配,我们返回false。
      • 否则,我们弹出栈顶的左方括号,表示匹配成功。

  4. 循环结束后,我们判断栈是否为空:

    • 如果栈为空,说明所有的左括号都被匹配,我们返回true。
    • 否则,说明还有未匹配的左括号,我们返回false。

  5. 在main函数中,我们使用getline函数读取一行输入。

  6. 我们调用isMatched函数判断表达式中的括号是否匹配,并输出相应的结果:

    • 如果匹配,输出"OK"。
    • 如果不匹配,输出"Wrong"。

对于输入样例[(])
,程序的执行过程如下:

  1. 读取输入字符串[(])。
  2. 调用isMatched函数:
    • 遇到[,将其压入栈中。
    • 遇到(,将其压入栈中。
    • 遇到],弹出栈顶的(,但是不匹配,返回false。
  3. 输出"Wrong"。

对于输入样例[([[][]])],程序的执行过程如下:

  1. 读取输入字符串[([[][]])]。
  2. 调用isMatched函数:
    • 遇到[,将其压入栈中。
    • 遇到(,将其压入栈中。
    • 遇到[,将其压入栈中。
    • 遇到],弹出栈顶的[,匹配成功。
    • 遇到[,将其压入栈中。
    • 遇到],弹出栈顶的[,匹配成功。
    • 遇到),弹出栈顶的(,匹配成功。
    • 遇到],弹出栈顶的[,匹配成功。
    • 遍历完表达式,栈为空,说明所有括号都匹配成功,返回true。
  3. 输出"OK"。

这个程序的时间复杂度为O(n),其中n为表达式的长度,因为我们需要遍历表达式的每个字符。空间复杂度为O(n),因为在最坏情况下,栈中需要存储所有的左括号。

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool isMatched(string exp) {
    stack<char> stk;

    for (char ch : exp) {
        if (ch == '(' || ch == '[') {
            stk.push(ch);
        } else if (ch == ')') {
            if (stk.empty() || stk.top() != '(') {
                return false;
            }
            stk.pop();
        } else if (ch == ']') {
            if (stk.empty() || stk.top() != '[') {
                return false;
            }
            stk.pop();
        }
    }

    return stk.empty();
}

int main() {
    string exp;
    getline(cin, exp);

    if (isMatched(exp)) {
        cout << "OK" << endl;
    } else {
        cout << "Wrong" << endl;
    }

    return 0;
}

1355：字符串匹配问题(strs)

为了判断输入的字符串中括号是否匹配,我们可以使用栈的数据结构。遍历字符串的每个字符,遇到左括号时将其压入栈中,遇到右括号时检查栈顶元素是否为对应的左括号,并且检查括号的嵌套顺序是否正确。下面是C++代码实现:

#include <iostream>
#include <string>
#include <stack>
#include <unordered_map>

using namespace std;

bool isValid(string s) {
    stack<char> stk;
    unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}, {'>', '<'}};
    
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{' || c == '<') {
            stk.push(c);
        } else {
            if (stk.empty() || stk.top() != pairs[c]) {
                return false;
            }
            stk.pop();
        }
    }
    
    return stk.empty();
}

int main() {
    int n;
    cin >> n;
    cin.ignore();  // 忽略换行符
    
    for (int i = 0; i < n; i++) {
        string s;
        getline(cin, s);
        
        if (isValid(s)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}

解析:

  1. 我们定义了一个函数isValid,用于判断字符串中的括号是否匹配。

    • 函数接受一个字符串s作为参数,表示输入的括号字符串。
    • 函数返回一个布尔值,表示括号是否匹配。

  2. 在isValid函数中,我们定义了一个栈stk,用于存储左括号。

    • 我们使用unordered_map定义了一个哈希表pairs,用于存储右括号和对应的左括号的映射关系。

  3. 我们使用for循环遍历字符串的每个字符:

    • 如果当前字符是左括号,我们将其压入栈中。
    • 如果当前字符是右括号,我们检查栈是否为空或者栈顶元素是否为对应的左括号:
      • 如果栈为空或者栈顶元素不是对应的左括号,说明括号不匹配,我们返回false。
      • 否则,我们弹出栈顶的左括号,表示匹配成功。

  4. 循环结束后,我们判断栈是否为空:

    • 如果栈为空,说明所有的左括号都被匹配,我们返回true。
    • 否则,说明还有未匹配的左括号,我们返回false。

  5. 在main函数中,我们首先读取一个整数n,表示接下来有n个括号字符串。

    • 我们使用cin.ignore()忽略换行符,以便正确读取后续的字符串。

  6. 我们使用for循环读取n个字符串,对于每个字符串:

    • 我们使用getline函数读取一行字符串。
    • 我们调用isValid函数判断字符串中的括号是否匹配,并输出相应的结果:
      • 如果匹配,输出"YES"。
      • 如果不匹配,输出"NO"。

这个程序的时间复杂度为O(n * m),其中n为字符串的数量,m为字符串的平均长度。对于每个字符串,我们需要遍历其中的每个字符,因此时间复杂度为O(m)。空间复杂度为O(m),因为在最坏情况下,栈中需要存储所有的左括号。

希望这个解析对你有所帮助。如果你还有任何疑问或建议,欢迎随时提出。

03-15 12:33
Powered by LMLPHP ©2024 天秀信息学奥赛 0.008230