首页 > 试题广场 > 括号配对问题
[编程题]括号配对问题
  • 热度指数:3140 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
括号配对问题

输入描述:
给定一个字符串S,请检查该字符串的括号是否配对,只含有"[", "]", "(", ")"


输出描述:
配对,返回true

不配对,返回false
示例1

输入

abcd(])[efg

输出

false
本题是很简单的一道题,当时学数据结构的书上讲到栈的部分正好就有本题的一个例子,即用栈
来保存左边括号,遇到右边括号便与当前栈顶进行匹配。但是本题在题目描述上有点粗糙,一开
始我只是输出flag,但是调试一直提示失败,然后才明白要输出的是字符串………………
#include<iostream>
#include<string>
#include<stack>
using namespace std;

int main()
{
    string s;
    cin>>s;
    stack<char> tmp;
    bool flag=false;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='[')
            tmp.push(s[i]);
        if(s[i]=='(')
            tmp.push(s[i]);
        if(s[i]==']')
        {
            if(tmp.empty())
            {
                flag=false;
                break;
            }
            else{
            char c=tmp.top();
            tmp.pop();
            if(c=='[')
                flag=true;
            else
            {
                flag=false;
                break;
            }
            }
        }
        if(s[i]==')')
        {
            if(tmp.empty())
            {
                flag=false;
                break;
            }
            else{
            char c=tmp.top();
            tmp.pop();
            if(c=='(')
                flag=true;
            else
            {
                flag=false;
                break;
            }
            }
        }
    }
    if(!tmp.empty())
        flag=false;
    if(flag)
        cout<<"true";
    else
        cout<<"false";
}

发表于 2019-10-14 21:02:52 回复(0)
""""
括号匹配,借助栈后进先出的性质
"""

if __name__ == "__main__":
    s = input().strip()
    ans = True
    flag = []
    for c in s:
        if c == '[' or c == '(':
            flag.append(c)
        elif c == ']':
            if not flag or flag.pop() != '[':
                ans = False
                break
        elif c == ')':
            if not flag or flag.pop() != '(':
                ans = False
                break
        else:
            pass
    if flag:
        ans = False
    print("true" if ans else "false")

编辑于 2019-07-12 11:22:20 回复(0)
循环结束后还应该判断一下栈内是否为空,若为空再返回true
例如:输入为"(()()()",返回应该为false,本例返回true
发表于 2019-06-26 09:27:41 回复(1)
#include <bits/stdc++.h>
using namespace std;
int main(){
    stack<char> st;
    bool flag=true;
    char c;
    while((c=cin.get())!='\n'){
        if(c=='('||c=='[')
            st.push(c);
        else if(c==')'){
            if(st.empty()||st.top()!='('){
                flag=false;
                break;
            }
            st.pop();
        }
        else if(c==']'){
            if(st.empty()||st.top()!='['){
                flag=false;
                break;
            }
            st.pop();
        }
    }
    cout<<(flag ? "true":"false");
    return 0;
}

发表于 2019-10-19 17:55:59 回复(0)
s = input()
left = ['[','(']
right = [']',')']
pair = {'[':']','(':')'}
res = []
for i in s:
    if i in left:
        res.append(i)
    if i in right:
        if res and pair[res[-1]]==i:
            res.pop()
        else:
            res.append(i)
            break
print('true' if not res else 'false')

发表于 2019-07-09 21:56:57 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    stack<char>st;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='('||s[i]=='[')
            st.push(s[i]);
        else if(s[i]==')')
        {
            if(st.top()=='(')
                st.pop();
            else
            {
                cout<<"false";
                return 0;
            }
        }
        else if(s[i]==']')
        {
            if(st.top()=='[')
                st.pop();
            else
            {
                cout<<"false";
                return 0;
            }
        }
        else
            continue;
    }
    if(st.empty())
        cout<<"true";
    else
        cout<<"false";
    return 0;
}

发表于 2019-07-03 10:31:03 回复(0)
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        Stack<Character> stack = new Stack<>();
        for (int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if (c == '(' || c == '[')
                stack.push(c);
            else if (c == ')'){
                if (stack.isEmpty() || stack.pop() != '(') {
                    System.out.println(false);
                    return;
                }
            }else if (c == ']'){
                if (stack.isEmpty() || stack.pop() != '[') {
                    System.out.println(false);
                    return;
                }
            }
        }
        if (stack.isEmpty())
            System.out.println(true);
        else
            System.out.println(false);
    }
}

发表于 2019-08-14 15:27:33 回复(0)
#include<stdio.h>
#define MAXSIZE 1000
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef struct{//顺序栈的定义 
	char c[MAXSIZE];
	int top;
}SeqStack;

void initStack(SeqStack *s);
int push(SeqStack *s, char c);
int pop(SeqStack *s, char *c);
int getTop(SeqStack *s, char *c);
int isTrue(char *temp, char c);
void outStack(SeqStack *s);

int main()
{
	SeqStack s, *s1 = &s;
	char str[MAXSIZE] = {"\0"};
	scanf("%s", str);
	initStack(s1);
	for(int i = 0; str[i] != '\0'; i++)
	{
//		outStack(s1);
		char b, *temp = &b;
		char c = str[i];
		switch(c)
		{
			case '(':
			case '[':
			case '{':
				push(s1, c);//压进栈内 
				break;
			case ')':
			case ']':
			case '}': 
				if(getTop(s1, temp) && isTrue(temp, c))	pop(s1, temp);
				else
				{
					printf("false\n");
					return 0;
				}
				break;
		}
	}
	if(s1->top != -1)
	{
		printf("false\n");
		return 0;
	}
	else printf("true\n");
	return 0;
}

//初始化顺序栈
void initStack(SeqStack *s)
{
	s->top = -1;
}

//顺序进栈运算
int push(SeqStack *s, char c)
{
	//将x置入s栈新栈顶
	if(s->top == MAXSIZE - 1)
	return FALSE;
	s->top++;
	s->c[s->top] = c;
	return TRUE;
}

//顺序栈出栈运算
int pop(SeqStack *s, char *c)
{
	//将栈S栈顶元素读出,放到x所指的存储空间中,栈顶指针保持不变
	if(s->top < 0)
	return FALSE;
	*c = s->c[s->top];
	s->top--;
	return TRUE;
} 

//将栈顶元素读出
int getTop(SeqStack *s, char *a)
{
	if(s->top < 0)
	return FALSE;
	*a = s->c[s->top];
	return TRUE;
}

//判断括号是否匹配 
int isTrue(char *temp, char c)
{
	switch(*temp)
	{
		case '(':
			if(c == ')') return TRUE;
			else return FALSE;
			break;
		case '[':
			if(c == ']') return TRUE;
			else return FALSE;
			break;
		case '{':
			if(c == '}') return TRUE;
			else return FALSE;
			break;
		default:
			return FALSE;
			break;
	}
}

发表于 2019-10-13 11:03:35 回复(0)
这个挺简单的,用一个stack保存之前的括号就行了,不过有一些边界条件需要考虑才能A
string = input()

stack = []

END = False
for s in string:
    if s.isalpha():
        continue
    elif s == '[' or s == '(':
        stack.append(s)
    elif s == ']':
        if len(stack) > 0 and stack[-1] == '[':
            stack.pop()
        else:
            print('false')
            END = True
            break
    elif s == ')':
        if len(stack) > 0 and stack[-1] == '(':
            stack.pop()
        else:
            print('false')
            END = True
            break

if not END: print('true' if len(stack) == 0 else 'false')


发表于 2019-09-08 14:46:40 回复(0)
class My_Stack:
    def __init__(self, elements=[]):
        self._elements = list(elements)
    
    def is_empty(self):
        #return not self._elements 
        return self._elements == []
    
    def push(self, element):
        self._elements.append(element)
    
    def pop(self):
        if self.is_empty():
            raise ValueError
        element = self._elements.pop()
        return element


def func(input_str):
    st = My_Stack()
    for ch in input_str:
        if ch == "[" or ch == "(":
            st.push(ch)
        elif ch == "]":
            if st.is_empty():
                print("false")
                return
            element = st.pop()
            if element != "[":
                print("false")
                return
        elif ch == ")":
            if st.is_empty():
                print("false")
                return
            element = st.pop()
            if element != "(":
                print("false")
                return
        else:
            continue
    if not st.is_empty():
        print("false")
    else:
        print("true")

        
input_str = input()
func(input_str)

发表于 2019-08-30 23:47:59 回复(0)