【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】

Rossy Yan

修改于 2024-12-26 10:33:47

5500

代码可运行

文章被收录于专栏：C++C++【Educoder实训】头歌实践教学平台

运行总次数：0

代码可运行

任务描述

本关任务：编写一个程序利用栈判断左、右圆括号是否配对。

相关知识

为了完成本关任务，你需要掌握：

栈对括号的处理。

栈对括号的处理

1. 基本原理

栈是一种遵循后进先出（Last In First Out，LIFO）原则的数据结构，非常适合用来处理括号匹配这类问题。在处理包含括号的表达式时，利用栈来记录左括号的出现情况，然后通过后续右括号的出现与之匹配来判断整个表达式中括号是否正确匹配。

2. 具体操作步骤

遇到左括号：进栈 Push ()

当遍历一个表达式（比如数学表达式或者编程语言中的代码块相关表达式等，像 “(3 + 4) * (2 - 1)” 这样的式子）时，一旦遇到左括号 “(”，就将这个左括号元素压入栈中。这相当于做一个记录，表示这里出现了一个等待匹配的左括号。例如，对于表达式 “((3 + 4))”，当扫描到第一个 “(” 时，栈为空，就把这个 “(” 压入栈中，此时栈里有一个元素就是这个左括号；接着扫描到第二个 “(”，同样把它压入栈，这时栈里就有两个左括号元素，按照后进先出的顺序，最上面（也就是最后进入栈）的元素是第二个 “(”，下面是第一个 “(”。

遇到右括号：若栈顶元素为左括号，则出栈 Pop ()；否则返回 false

继续遍历表达式，当遇到右括号 “)” 时，需要查看栈的情况来判断括号匹配是否正确。此时会去检查栈顶元素，如果栈顶元素恰好是左括号，那就说明当前这个右括号找到了与之匹配的左括号，是合理的括号结构，所以把栈顶的这个左括号元素从栈中弹出（即出栈操作）。例如，对于前面提到的 “((3 + 4))”，当扫描到第一个 “)” 时，查看栈顶元素，发现是左括号，于是将这个栈顶左括号出栈；接着扫描到第二个 “)”，再查看栈顶元素（此时栈里还有一个左括号，就是最开始压入的那个），发现依然是左括号，也将其出栈。这样整个表达式的括号匹配就是正确的。但如果遇到右括号时，栈顶元素不是左括号（比如栈已经为空了，或者栈顶是别的字符等情况），那就意味着这个右括号没有与之匹配的左括号，括号结构是错误的，此时就要返回 false。例如，对于表达式 “) (3 + 4)”，一开始就遇到右括号，此时栈是空的，没有可以与之匹配的左括号，所以可以直接判定这个表达式的括号匹配是不正确的，返回 false。

当遍历表达式结束，且栈为空时，则返回 true，否则返回 false

当把整个表达式都遍历完了之后，需要再检查一下栈的状态。如果栈为空，那就说明表达式里所有的左括号都找到了对应的右括号，整个括号结构是匹配正确的，这种情况下返回 true。例如 “(3 + 4) * (2 - 1)” 这个表达式，在遍历完整个式子后，之前压入栈的左括号都因为遇到对应的右括号而出栈了，最后栈为空，所以其括号匹配正确，返回 true。然而，如果遍历完表达式后栈里还有元素（也就是还有左括号没有匹配到右括号），那就说明括号匹配存在问题，此时要返回 false。比如表达式 “((3 + 4”，当遍历完这个式子后，栈里还剩下一个左括号，说明有左括号没被匹配，括号结构不正确，返回 false。

3. 示例解释

示例代码如下：

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

using namespace std;

bool checkBrackets(const string& expression) {
    stack<char> st;  // 创建一个用于存储括号的栈
    for (char ch : expression) {  // 遍历表达式中的每一个字符
        if (ch == '(') {  // 如果是左括号
            st.push(ch);  // 将左括号压入栈
        } else if (ch == ')') {  // 如果是右括号
            if (st.empty()) {  // 先检查栈是否为空
                return false;  // 若为空，说明没有匹配的左括号，直接返回false
            }
            st.pop();  // 如果栈不为空，弹出栈顶元素（匹配的左括号）
        }
    }
    return st.empty();  // 遍历完表达式后，若栈为空则括号匹配正确，返回true，否则返回false
}

int main() {
    string expression = "(3 + 4) * (2 - 1)";
    bool result = checkBrackets(expression);
    if (result) {
        cout << "括号匹配正确" << endl;
    } else {
        cout << "括号匹配错误" << endl;
    }
    return 0;
}

在上述代码中：

checkBrackets函数：
- 首先定义了一个std::stack<char>类型的栈st，用来存放括号字符。
- 然后通过for循环遍历输入的字符串expression中的每一个字符。
- 当遇到字符'('时，调用st.push(ch)将左括号压入栈中，模拟了遇到左括号进栈的操作。
- 当遇到字符')'时，先通过st.empty()判断栈是否为空，如果为空意味着没有可以与之匹配的左括号，直接返回false；若栈不为空，则调用st.pop()将栈顶元素（也就是对应的左括号）弹出，模拟了遇到右括号且栈顶是左括号时出栈的操作。
- 最后在遍历完整个表达式后，通过return st.empty();来判断栈是否为空，如果为空就表示所有的左括号都有对应的右括号匹配，返回true，否则返回false。
main函数：
- 定义了一个测试用的字符串expression，这里可以替换成你想要测试括号匹配情况的任意表达式字符串。
- 调用checkBrackets函数检查括号匹配情况，并将返回结果保存在result变量中。
- 根据result的值输出相应的提示信息，告知用户括号匹配是正确还是错误。

提示：你可以修改main函数中expression变量的内容来测试不同的表达式括号匹配情况，比如可以将其改成"((3 + 4)"或者"(3 + 4)))"等，查看对应的输出结果是否符合预期。

测试说明

平台会对你编写的代码进行测试：

测试输入：

(())

预期输出：

配对

测试输入：

(()))

预期输出：

不配对

开始你的任务吧，祝你成功！

通关代码

// 请在Begin-End之间添加你的代码，
//利用栈判断左、右圆括号是否配对//
//(1)如果配对，返回true，输出“配对”//
//(2)如果不配对，返回false，输出“不配对”//
/********** Begin *********/
#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool areParenthesesBalanced(const string &expression){
    stack<char> s;

    for(char ch : expression){
        if(ch == '('){
            s.push(ch);
        }else if(ch == ')'){
            if(s.empty()||s.top() != '('){
                return false;
            }
            s.pop();
        }
    }
    return s.empty();
}

int main(){
    string input;

    cin >> input;

    if(areParenthesesBalanced(input)){
        cout<<"配对"<<endl;
    }else{
        cout<<"不配对"<<endl;
    }
    return 0;
}


/********** End **********/