信息学奥赛一本通 1353：表达式括号匹配(stack) | 洛谷 P1739 表达式括号匹配

【题目链接】

ybt 1353：表达式括号匹配(stack)
洛谷 P1739 表达式括号匹配

【题目考点】

1. 栈

【解题思路】

遍历整个字符串，遇到左括号时入栈，遇到右括号时，应该出栈一个左括号。如果遇到右括号时栈空，说明存在右括号无法配对。
在遍历结束后，如果栈不为空，说明存在左括号无法配对。

可以用数组及表达式实现栈功能，可以使用函数实现栈功能，可以自己写栈类，也可以使用STL中是stack。

【题解代码】

解法1：用数组及表达式实现栈

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[260];
    char stk[260];
    int top = 0;
    scanf("%s", s);
    bool isMatch = true;
    for(int i = 0; s[i] != '@'; ++i)
    {
        if(s[i] == '(')
            stk[++top] = s[i];//入栈 
        else if(s[i] == ')')
        {
            if(top == 0)//判断是否栈空。有右括号时遇到空栈 
            {
                isMatch = false;
                break;
            }
            else
                --top;//出栈 
        }
    }
    if(top != 0)//如果最后栈不空 
        isMatch = false;
    if(isMatch)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

解法2：函数实现栈功能

#include<bits/stdc++.h>
using namespace std;
char stk[260];
int top = 0;
void push(char c)
{
    stk[++top] = c;
}
bool empty()
{
    return top == 0; 
}
void pop()
{
    top--;
}
int main()
{
    char s[260];
    scanf("%s", s);
    bool isMatch = true;
    for(int i = 0; s[i] != '@'; ++i)
    {
        if(s[i] == '(')
            push(s[i]);//入栈 
        else if(s[i] == ')')
        {
            if(empty())//判断是否栈空。有右括号时遇到空栈 
            {
                isMatch = false;
                break;
            }
            else
                pop();//出栈 
        }
    }
    if(empty() == false)//如果最后栈不空 
        isMatch = false;
    if(isMatch)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

解法3：C++STL 实现栈功能

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[260];
    scanf("%s", s);
    stack<char> stk;
    bool isMatch = true;
    for(int i = 0; s[i] != '@'; ++i)
    {
        if(s[i] == '(')
            stk.push(s[i]);//入栈 
        else if(s[i] == ')')
        {
            if(stk.empty())//判断是否栈空。有右括号时遇到空栈 
            {
                isMatch = false;
                break;
            }
            else
                stk.pop();//出栈 
        }
    }
    if(stk.empty() == false)//如果最后栈不空 
        isMatch = false;
    if(isMatch)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31