【P1739 表达式括号匹配】百度翻译大雾：堆还是栈？

極灬青龙 · 2020-11-24 17:03:38 · 个人记录

没错，我又来水题解了

欢迎来到某菜鸟的第5篇题解

【题目：传送门】

这一道题是让你来匹配左右小括号的

那么首先，先来输入表达式

直接用字符串就行了

所以并不用管@的问题

直接输入：

string expr;
cin >> expr;

以下为代码核心

敲黑板（Duang~）

二敲（Dur~）

水字数ing

咳咳，好了继续

    bool flag = false;
    for(int i=0; i<expr.size() - 1; i++)
    {
        if(expr[i]=='(')
            s.push(expr[i]);
        if(expr[i]==')')
        {
            if(s.empty())
            {
                flag = true;
                break;
            }
            s.pop();
        }
    }

先放一段代码大家细品一下

这里的s是一个栈

（其实用栈还是用什么其他的队列什么的没什么区别）

话说百度翻译的stack是“堆栈”的意思

【百度翻译热心链接】

这一段的意思就是

每一次检测到一个左括号

就把它入栈

每次检测到右括号的时候

就检测一下栈里有没有左括号

~~有的话就是一对了~~

（撒狗粮ing）

如果没有的话，就说明这个右括号前面没有能与之配对的左括号

然后就可以改变一下结果

所以……？

没有所以了，这道题做完了

㵘㵘㵘㵘㵘㵘㵘（màn）

最后在放一下整个的代码

#include <string.h>
#include <iostream>
#include <stdio.h>
#include <stack>

using namespace std;

int main(){
    stack<char> s;
    string expr;
    cin >> expr;
    bool flag = false;
    for(int i=0; i<expr.size() - 1; i++)
    {
        if(expr[i]=='(')
            s.push(expr[i]);
        if(expr[i]==')')
        {
            if(s.empty())
            {
                flag = true;
                break;
            }
            s.pop();
        }
    }
    if(flag || !(s.empty()))
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
    return 0;
}

其实这道题的代码还是有不少问题的

比如发现配对不成功时就可以直接输入NO然后return了

再比如我也不知道为什么我没有用万能头

所以修改后的代码是这样的：

#include <bits/stdc++.h> 

using namespace std;

int main(){
    stack<char> s;
    string expr;
    cin >> expr;
    bool flag = false;
    for(int i=0; i<expr.size() - 1; i++)
    {
        if(expr[i]=='(')
            s.push(expr[i]);
        if(expr[i]==')')
        {
            if(s.empty())
            {
                cout << "NO" << endl;
                return 0;
            }
            s.pop();
        }
    }
    cout << "YES" << endl;
    return 0;
}

至于能不能过，我也不知道了

毕竟我是现场改的

最后再简单提一下，这道题不能只简单的判断左右括号的数量是否一致

不然的话会出一些Wonderful Answer（WA）

例如：）（