首页 > 试题广场 >

括号匹配

[编程题]括号匹配

热度指数：1974 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个只包含括号的字符串，判断字符串是否有效。其中，括号种类包含： ‘(’，’)’，’{’，’}’，’[’，’]'。有效字符串需满足：1) 左括号必须用相同类型的右括号闭合；2）左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串

示例1

输入

"{[]}"

输出

true

示例2

输入

"([)]"

输出

false

示例3

输入

"([]"

输出

false

算法知识视频讲解

scaler7

public boolean IsValidExp (String s) {
         String left = "{[(";
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {

            char c2 = s.charAt(i);
            if(stack.isEmpty() || left.contains(c2+"")){
                stack.push(c2);
                continue;
            }else{
                Character c1 = stack.peek();
                if(c2=='}' && c1=='{'){
                    stack.pop();
                }
                if(c2==']' && c1=='['){
                    stack.pop();
                }
                if(c2==')' && c1=='('){
                    stack.pop();
                }
            }
        }
        return stack.isEmpty();
    }

发表于 2022-01-14 10:40:53 回复(0)

牛客286755060号

python

#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def IsValidExp(self , s ):
        # write code here
        if s =="":
            return True
        while "{}" in s&nbs***bsp;"()" in s&nbs***bsp;"[]" in s:
            s = s.replace('{}','')
            s = s.replace('[]','') 
            s = s.replace('()','')
        if s=='':
            return True
        else:
            return False

发表于 2021-09-15 16:09:25 回复(0)

Cactus_tt

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
   bool IsValidExp(string s) {
        // write code here
        char fh[50];
        strcpy(fh,s.c_str());
        int len=strlen(fh);
        if(len==0)
          return true;
        if(len%2!=0)
          return false;
        for(int i=0;i<len;i++)
           {
           	if(fh[i]=='(')
           	   {
           	   	if(i>=1)
           	   	{
           	   		if(fh[i-1]==' '&&fh[i+1]==' ')
           	   		  return false;
					  }
           	   	for(int j=i+1;j<len;j++)	
           	   	{
					if(fh[j]==')')
					{
					fh[i]=' ';
					fh[j]=' ';
					break;
					}
				    continue;
				 } 
			}
			 if(fh[i]=='[')
           	   {
           	   	if(i>=1)
           	   	{
           	   		if(fh[i-1]==' '&&fh[i+1]==' ')
           	   		  return false;
					  }
           	   	for(int j=i+1;j<len;j++)	
           	   	{
					if(fh[j]==']')
					{
					fh[i]=' ';
					fh[j]=' ';
					break;
					}
				    continue;
				 } }
			 if(fh[i]=='{')
           	   {
           	   	if(i>=1)
           	   	{
           	   		if(fh[i-1]==' '&&fh[i+1]==' ')
           	   		  return false;
					  }
           	   	for(int j=i+1;j<len;j++)	
           	   	{
					if(fh[j]=='}')
					{
					fh[i]=' ';
					fh[j]=' ';
					break;
					}
				    continue;
				 } 	 
				  }
	}
		  for(int i=0;i<len;i++)
		  {
		  	if(fh[i]!=' ')
		  	   return false;
		  }
		  return true;	    
}
};

遇到问题解决问题哈哈哈硬是没用任何数据结构（苦笑.jpg

发表于 2021-04-14 23:43:57 回复(1)

苏沐沐橙

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean IsValidExp (String s) {
        // write code here
        Stack<Character> stack = new Stack<>();
        for(char ch : s.toCharArray()){
            if(ch == '[') stack.push(']');
            else if(ch == '(') stack.push(')');
            else if(ch == '{') stack.push('}');
            else if(stack.isEmpty() || !stack.pop().equals(ch)) return false;
        }
        return stack.isEmpty();
    }
}

发表于 2021-08-25 17:42:55 回复(0)

湮灭丶星空

这题考察栈，遇见( [ { 入栈，遇见) ] } 就出栈然后判断是否跟左括号相应的匹配，匹配就继续，不匹配直接返回

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean IsValidExp (String s) {
        if(s.length()==1)return false;
        LinkedList list=new LinkedList();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{')
                list.add(s.charAt(i));
            if(s.charAt(i)==')'){
                 if(list.size()==0)return false;
                    char a=(char)list.pollLast();
                    if(a!='(')return false;          
            }
             if(s.charAt(i)==']'){
                 if(list.size()==0)return false;
                    char a=(char)list.pollLast();
                    if(a!='[')return false;          
            }
             if(s.charAt(i)=='}'){
                 if(list.size()==0)return false;
                    char a=(char)list.pollLast();
                    if(a!='{')return false;          
            }
               
            
               
        }
        return true;
        
    }
}

发表于 2021-04-17 16:29:14 回复(1)

C/C++

wit1905120602

C++，用的栈，不知道为什么数组长度是50，有人能解答吗

#include<stack>

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool IsValidExp(string s) {
        char c[50];
        strcpy(c,s.c_str());
        int len=strlen(c);
        if(len==0)return true;
        if(len%2)return false;
        stack<char> stk;
        for(int i=0;i<len;i++)
        {
            if(c[i]=='{'){
                stk.push('}');
            }else if(c[i]=='['){
                stk.push(']');
            }else if(c[i]=='('){
                stk.push(')');
            }else if(stk.empty()||stk.top()!=c[i]){
                return false;
            }else {
                stk.pop();
            }
        }return stk.empty();
    }
};

发表于 2022-10-02 20:03:16 回复(0)

牛客541156809号

func IsValidExp( s string ) bool {
    // write code here
    if s == "" {
        return true
    }
     
    var stack []byte
     
    for i:=0; i<len(s); i++ {
        if s[i] == '{' {
            stack = append(stack, '}')
        }else if  s[i] == '('{
            stack = append(stack, ')')
        }else if  s[i] == '[' {
            stack = append(stack, ']')
        }else {
            if len(stack) <= 0 {
                return false
            }
            top := stack[len(stack)-1]
            if top !=  s[i] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
     
    return len(stack) == 0
}

发表于 2022-01-02 15:07:57 回复(0)

钛极

//  9/10，剩下的不知道什么情况
import java.util.*;
 
 
public class Solution {
    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean IsValidExp (String s) {
        int len = s.length();
        Stack<Character> stack = new Stack<>();
        stack.push(s.charAt(0));
        for (int i = 1; i < len; i++) {
            char c = s.charAt(i);
            if (stack.isEmpty()){
                stack.push(c);
            }else{
                if (c == ')'){
                    if (stack.peek() !='('){
                        return false;
                    }else {
                        stack.pop();
                    }
                }else
                if (c == '}'){
                    if (stack.peek() !='{'){
                        return false;
                    }else {
                        stack.pop();
                    }
                }else
                if (c == ']'){
                    if (stack.peek() !='['){
                        return false;
                    }else {
                        stack.pop();
                    }
                }else
                stack.push(c);
            }
 
        }
        if (stack.isEmpty()){
            return true;
        }
        return false;
    }
}

发表于 2021-09-13 14:38:58 回复(0)

牛客159766845号

golang单调栈

func IsValidExp( s string ) bool{

// write code here

a := map[byte]byte{'}':'{', ']':'[', ')':'('}

res := []byte{}

fori := range s{

ifs[i] == '{'|| s[i] == '['|| s[i] == '('{

res = append(res, s[i])

}elseiflen(res) > 0 && a[s[i]] == res[len(res)-1]{

res = res[:len(res)-1]

}else{

returnfalse

}

returnlen(res) == 0

}

发表于 2021-09-01 09:43:40 回复(0)

元气森林打气水

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean IsValidExp (String s) {
        // write code here
        Stack<String> stack = new Stack<String>();
        if (s.length() == 0) {
            return true;
        }
        for(int i=0;i<s.length();i++){
            String input = s.substring(i,i+1);
            if(input.equals("[") || input.equals("{") || input.equals("(")){
                stack.push(input);
            }else {
                if(stack.size()==0){
                    return false;
                }
                String output = stack.pop();
                switch (output){
                    case "{":
                        if(!input.equals("}")){
                            return false;
                        }
                        break;
                    case "[":
                        if(!input.equals("]")){
                            return false;
                        }
                        break;
                    case "(":
                        if(!input.equals(")")){
                            return false;
                        }
                        break;
                }
            }
        }
        return true;
    }
}

发表于 2021-06-29 21:30:20 回复(0)

Java

old李

import java.util.Scanner;
import java.util.Stack;
public class 有效的括号 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            boolean valid = isValid(str);
            System.out.println(valid);
        }
        scanner.close();
    }

    private static boolean isValid(String str) {
        if(str == null) {
            return false;
        }

        Stack<Character> stack = new Stack<>();
        for(char ch: str.toCharArray()) {
            if(!valid(ch)) {
                return false;
            }
            if(isLeft(ch) || stack.isEmpty()) {
                stack.push(ch);
            } else {
                Character left = stack.pop();
                if(!isValid(left, ch)) {
                    stack.push(left);
                    stack.push(ch);
                }
            }
        }

        return stack.isEmpty();
    }

    private static boolean isValid(char left, char right) {
        return (left == '(' && right == ')')
                || (left == '[' && right == ']')
                || (left == '{' && right == '}');
    }
    private static boolean isLeft(char ch) {
        return ch == '(' || ch == '[' || ch == '{';
    }
    private static boolean valid(char ch) {
        return ch == '(' || ch == ')'
               || ch == '[' || ch == ']'
               || ch == '{' || ch == '}';
    }
}

发表于 2021-05-08 00:02:58 回复(1)

Angel20181107233280

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean IsValidExp (String s) {
        // write code here
        if(s.length() == 0) {
            return true;
        }
        if(s.length() % 2 != 0) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '{') {
                stack.push('}');
            }else if(c == '[') {
                stack.push(']');
            }else if(c == '(') {
                stack.push(')');
            }else {
                Character pop = stack.pop();
                if(pop != c) {
                    return false;
                }
            }
        }
        return true;
    }
}

发表于 2021-04-21 15:24:18 回复(0)