【题目描述】

【输入】

【输出】

【输入样例】

2*(x+y)/(1-x)@

【输出样例】

YES

【提示】

(25+x)*(a*(a+b+b)@

NO

#include<bits/stdc++.h>
using namespace std;
int main(){
	char a[255];
	int n=0;
	cin>>a;
	int i=0;
	while(true){
		if(a[i]=='@')break;
		if(a[i]=='(')n++;
		if(a[i]==')')n--;
        i++;
	}
	if(n==0){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
}//既然看了我的代码，就点个赞呗（不多，就一个赞）！！！

 【代码】（第二种方法）：

【思路点拨】

把所有的‘（’统计起来放进栈n里，再把‘）’统计起来放进栈m里，比较两个栈的元素的数量是否相等，简单的说就是‘（’的数量与‘）’的数量是否相等。

#include<bits/stdc++.h>
using namespace std;
int main(){
	stack<char> n,m;
	char a[255],b;
	int c=0,d,i=0;
	cin>>a;
	while(1){
		if(a[i]=='@')break;
		if(a[i]=='(')n.push(a[i]);
		if(a[i]==')')m.push(a[i]);
		i++;
	}
	c=n.size();
	d=m.size();
	if(c!=d){
		cout<<"NO";
	}else{
		cout<<"YES";
	}
}//既然看了我的代码，就点个赞呗（不多，就一个赞）！！！

20. 有效的括号（力扣）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
 

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

 思路一（利用栈）

对字符串从左到右进行处理

如果是左括号（包括 ( , [ , {  ），则入栈；

如果是右括号，则判断栈顶元素是否与右括号匹配

1. 栈空，右括号无法匹配--则直接可以得到结果--false
2. 栈顶元素与右括号不匹配--则直接可以得到结果--false
3. 栈顶元素与右括号匹配--则弹出栈顶元素

处理完字符串后，再判断栈是否为空

• 栈空--说明字符串中的左右括号刚好匹配
• 栈不空--说明左括号有剩余

class Solution {
public:
    bool isValid(string s) {
        stack<char> v;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                v.push(s[i]);
            }
            else if (s[i] == ')' || s[i] == ']' || s[i] == '}')
            {

                    if (v.empty()) { return false; }
                    switch (s[i])
                    {
                    case ')':
                    {
                        if (v.top() == '(')
                        {
                            v.pop();
                        }
                        else
                            return false;
                        break;
                    }
                    case ']':
                    {
                        if (v.top() == '[')
                        {
                            v.pop(); 
                        }
                        else
                            return false;
                        break;
                    }
                    case '}':
                    {
                        if (v.top() == '{')
                        {
                            v.pop();
                        }
                        else
                            return false;
                        break;
                    }
                    }
            }
       
        }
        
        if (v.empty())
            return true;
        else
            return false;
    }
};

题目

问题描述

现在，有一行括号序列，请你检查这行括号是否配对。

输入

第一行输入一个数N

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

样例输入 复制

3
[(])
(])
([[]()])

样例输出 复制

No
No
Yes

解法二（利用数组）

感觉我好像写复杂了

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
bool f(char a, char b)
{
	if (( a == '(' && b == ')' )|| (a == '{' && b == '}') || ( a == '[' && b == ']'))
		return true;
	else
		return false;
}
int main()
{
	char ch[100];
	int n;
	cin >> n;
	while (n--)
	{
		ch[0] = '1';
		cin >> &ch[1];
		int len = strlen(ch);
		for (int i = 2; i <=len; i++)
		{
			while(f(ch[i-1],ch[i])==true)
			{
				for (int j = i - 1; j <=len - 1; j++)  //括号匹配时--覆盖匹配的元素
				{
					ch[j] = ch[j + 1];   
				}
				ch[len-1] = '\0';  //处理字符串结尾
				len--;             //数组长度减小
				if (i == 0)
				{
					cout << "YES" << endl;
					break;
				}
				for (int j = i - 1; j <=len - 1; j++)
				{
					ch[j] = ch[j + 1];
				}
				ch[len-1] = '\0';   //处理字符串结尾
				len--;
				i--;
			}
		}
		if (strlen(ch) == 1)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}

总结归纳

1. 算法思想： 设置一个空栈，顺序读取括号。读取左括号时，将括号入栈；读取右括号时，弹出栈顶元素，栈顶即是与之匹配的最近的左括号。
2. 匹配不成功的三种情况：(1)读取右括号时，此时栈空，没有与之匹配的左括号。(2)读取右括号时，弹出的栈顶左括号与之不匹配。(3)顺序读取括号后，栈不为空，即有括号未被匹配。

代码实践

/*
栈的括号匹配
*/

#include <iostream>

#define MaxSize 10 // 栈中元素的最大个数

using namespace std;

typedef char ElemType;

// 栈的结构
struct SqStack {
    ElemType data[MaxSize]; // 静态数组存放栈顶元素
    int top;                // 栈顶指针
};

// 初始化栈
void InitStack(SqStack &S) { S.top = -1; }

// 判断栈空
bool StackEmpty(SqStack S) {
    if (S.top == -1) {
        return true;
    } else {
        return false;
    }
}

// 入栈
bool Push(SqStack &S, ElemType x) {
    if (S.top == MaxSize - 1) {
        return false;
    } else {
        S.top++;
        S.data[S.top] = x; // S.top指向栈顶
        return true;
    }
}

// 出栈
bool Pop(SqStack &S, ElemType &x) {
    if (S.top == -1) { // 栈空
        return false;
    } else {
        x = S.data[S.top--]; // 先赋值再--
        return true;
    }
}

// 括号匹配
bool BracketMatch(char str[], int len) {
    SqStack S;
    InitStack(S);
    for (int i = 0; i < len; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            Push(S, str[i]); // 扫描到左括号，入栈
        } else {
            if (StackEmpty(S)) { // 扫描到右括号且当前栈空
                return false;
            }
            char topElem;
            Pop(S, topElem); // 栈顶元素出栈
            if (str[i] == ')' && topElem != '(') {
                return false;
            }
            if (str[i] == ']' && topElem != '[') {
                return false;
            }
            if (str[i] == '}' && topElem != '{') { // 弹出的括号与遍历的括号不匹配
                return false;
            }
        }
    }
    return StackEmpty(S); // 括号全部匹配完后，栈空为成功
}

// 获取字符串数组长度
int GetLength(char str[]) {
    int i = 0;
    while (str[i] != '\0') {
        i++;
    }
    return i;
}

int main() {
    char str[MaxSize];
    cin >> str;
    int len = GetLength(str);
    bool result = BracketMatch(str, len);
    cout << result << endl;
    return 0;
}