使用栈解决表达式括号匹配问题

使用栈解决表达式括号匹配问题

引用

CSDN

1.

https://blog.csdn.net/m0_62531913/article/details/137616921

本文将介绍如何使用栈数据结构来解决表达式括号匹配问题。这是一个经典的算法问题，通常出现在编程竞赛和面试中。通过本文，你将学习到栈的基本操作以及如何将其应用于实际问题的解决。

题目描述

给定一个字符串，判断其中的括号是否匹配。具体来说，就是判断字符串中的每个左括号 '(' 是否都有一个对应的右括号 ')'，且括号的顺序正确。

思路分析

使用栈（stack）是解决这类问题的经典方法。栈是一种后进先出（LIFO）的数据结构，非常适合用来处理括号匹配问题。

首先定义一个栈 stack<char> st;

遍历字符串，只需要看左括号和右括号，其他的字符不用考虑。

当字符为左括号时，压栈 st.push(')');

当字符为右括号时，我们看栈是否为空，如果栈为空，括号就不合法。否则，我们出栈 st.pop();

最后当遍历完字符串后，我们看栈是否为空。为空就说明括号合法，否则说明不合法。

代码实现

下面是完整的C++代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s; cin >> s;
    stack<int> st;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') st.push('(');
        else if (s[i] == ')') {
            if (st.empty()) {
                cout << "NO" << endl;
                return 0;
            }
            st.pop();
        }
    }
    if (st.empty()) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}