洛谷P1739题解

洛谷P1739

题目信息：

题目传送门：https://www.luogu.com.cn/problem/P1739
知识点：栈

题目简述：

有一个字符串由数字+-*/构成，以@结尾，要求判断里面的括号是否配对

题目分析：

该题要判断括号是否配对，这与其它元素无关，只需关注括号即可
考虑这样的问题()((()())，很显然第三个(是多余的，但是如何用编程描述呢？
我们在作这个问题的时候其实是让）和最近的左括号配对，如果用栈储存(每次遇到)就拿出一个(可以发现这符合栈后进先出的原则
因此这道题可以用栈解决

伪代码：

扫字符串{
  if ( 入栈
  else if ）{
      if 空 不合法；return 0；
      else 出栈
  }
}
if 空 YES
else NO

具体代码如下：

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;

const int maxn = 260;
char s[maxn];
stack<int> stk;

int main() {
    scanf("%s", s);
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        if (s[i] == '@') break;

        if (s[i] == '(') {
            stk.push(1);
        }
        else if (s[i] == ')') {
            if (stk.empty()) {
                printf("NO\n");
                return 0;
            }
            else {
                stk.pop();
            }
        }
    }

    printf("%s\n", stk.empty() ? "YES" : "NO");
    return 0;
}

最后