STL容器：栈 1350 表达式括号匹配题解

yuanbao

栈是一种后进先出（LIFO）的数据结构，可以通过 push() 函数将元素压入栈顶，通过 pop() 函数将栈顶元素弹出。栈还有一个 top() 函数，用于返回栈顶元素，但不会将其弹出。通过 empty() 函数可以判断栈是否为空，通过 size() 函数可以返回栈中元素的个数。

在这个问题中，我们使用了栈来判断表达式中的括号是否匹配。每当遇到一个左括号时，就将其压入栈中；每当遇到一个右括号时，就将栈顶元素弹出，同时判断其是否为左括号。如果是左括号，则说明该右括号与之匹配，将左右括号个数均减 1；否则说明该表达式不符合要求，将右括号个数加 1，继续向后遍历。最后，判断栈是否为空且右括号个数是否为 0，若是，则说明表达式括号匹配，输出"YES"，否则输出"NO"。

C++ STL 库中的栈容器可以通过 #include <stack> 引入。栈的定义方式为 stack<type> name;，其中 type 为栈中元素的类型，name 为栈的名称。常用的函数包括 push()、pop()、top()、empty() 和 size()。

1. #include <iostream>
   
2. #include <string>
   
3. #include <stack>
   
4. using namespace std;
   
5. 
   
6. stack<char> p; // 用于存储左括号的栈
   
7. string st; // 用于存储输入的字符串
   
8. int ind, cnt; // ind: 左括号个数, cnt: 右括号个数
   
9. 
   
10. int main() {
    
11.     getline(cin, st); // 读取输入的字符串
    
12.     int len = st.size(); // 获取字符串的长度
    
13.     for (int i = 0; i < len; i++) { // 遍历字符串中的每一个字符
    
14.         if (st[i] == '@') break; //当遍历到字符@跳出循环
    
15.         if (st[i] == '(') { // 如果该字符为左括号
    
16.             p.push(st[i]); // 将其压入栈中
    
17.             ind++; // 左括号个数加1
    
18.         }
    
19.         if (st[i] == ')') { // 如果该字符为右括号
    
20.             cnt++; // 右括号个数加1
    
21.             if (ind && p.top() == '(') { // 如果此时左括号个数不为0且栈顶为左括号
    
22.                 p.pop(); // 弹出栈顶元素
    
23.                 ind--; // 左括号个数减1
    
24.                 cnt--; // 右括号个数减1
    
25.             }
    
26.         }
    
27.     }
    
28.     if (p.empty() && !cnt) cout << "YES"; // 如果栈为空且右括号个数为0，说明括号匹配，输出"YES"
    
29.     else cout << "NO"; // 否则输出"NO"
    
30.     return 0;
    
31. }
    

复制代码

oliver

没有看到代码哦

yuanbao

雷老师，代码加上了