首页 > 试题广场 >

假设有如下字符串： (234453)[234]{2324}

[问答题]

假设有如下字符串： (234453)[234]{2324} 现在，要求编程分析其括号配对是否正确。请自行选择下列两种方案之一实现该程序：
方案一：不考虑括号优先级，只考虑配对正确性；方案二：考虑括号优先级，比如{1[2（3）4]5} 是正确的。但是[1{2}3]是不正确的。

查看答案及解析

推荐

Owen

方案一：
使用栈，碰到左括号入栈，碰到右括号出栈，看最后栈是否空，是否还有未匹配完的右括号。
方案二：
思路同上，但是检查压栈时要对括号做优先级检查。

编辑于 2014-12-05 10:26:02 回复(0)

FantasyLin

以下是我用Java编写的代码，解决的是方案二。是用“栈”来辅助解决的。具体代码如下：

package javaTest;

import java.util.Stack;

public class JavaTest {

    public static boolean solve(StringBuilder str) {
    	
    	if (str.length() == 0) return false;
    	
    	Stack<Character> stack = new Stack<Character>();
    	
    	for (int i = 0; i < str.length(); i++) {
    		char ch = str.charAt(i);
    		switch (ch) {
    		case '{':
    		case '[':
    		case '(':
    			if (!stack.empty()) {
    				char chX = stack.peek();
    				if ((ch == '{' && chX == '{')
    						|| (ch == '{' && chX == '[')
    						|| (ch == '{' && chX == '(')
    						|| (ch == '[' && chX == '[')
    						|| (ch == '[' && chX == '(')
    						|| (ch == '(' && chX == '(')) {
    					return false; //左括号入栈前，要判断优先级，如果不符合，则false
    				} else {
    					stack.push(ch); //符合优先级，则入栈
    				}
    			} else {
        			stack.push(ch);
    			}
    			break;
    		case '}':
    		case ']':
    		case ')':
    			if (!stack.empty()) {
    				char chX = stack.pop();
    				if ((ch == '}' && chX != '{')
    						|| (ch == ']' && chX != '[')
    						|| (ch == ')' && chX != '('))
    					return false;
    			} else {
    				return false;
    			}
    			break;
    		default:
    			break;
    		}
    	}
    	
    	if (!stack.empty()) //栈内不为空，则证明还有左括号没有匹配，所以false
    		return false;
    	else
    		return true;
    }
    
	public static void main(String[] args) {
		StringBuilder str = new StringBuilder();
		str.append("(){}[]{[]}([])");
		System.out.print(solve(str));
	}
}

编辑于 2016-10-05 15:07:58 回复(0)

指上弹兵赵小括

方案1：

使用栈，碰到做半部分入栈，如(、[、{，碰到右半部分和栈顶比较，配对则出栈，不配对则返回false；最后判断栈是否为空。

方案2：

思路同上，压栈需判断优先级；

发表于 2015-09-09 15:41:21 回复(0)

Tim.Bing

跟楼上的方案类似，也是使用数据结构栈来解决，与解析xml一样，有开始标签结束标签。

public static boolean check1(String str) {
 Stack<String> stack = new Stack<String>();
 char[] charArr = str.toCharArray();

 for(int i=0; charArr!=null && i<charArr.length; i++) {
     if("{}[]()".indexOf(charArr[i])>-1) {
         if(stack.size()==0) {
             stack.push(String.valueOf(charArr[i]));
         } else {
             String top = stack.peek();
             String tmp = top + charArr[i];

             if("{}[]()".indexOf(tmp)>-1) {
                 stack.pop();
             } else {
                 stack.push(String.valueOf(charArr[i]));
             }
             // 方案2与方案1不同的就是，在这个地方加一个优先级判断
             if("([{".indexOf(tmp)>-1 || "({".indexOf(tmp)>-1)
                 return false;  
        }
     }
 }
 return stack==null || stack.size()==0?true:false;
 }

编辑于 2015-01-14 21:45:26 回复(0)

不和你哔哔

如果要求中括号、大括号不能单独出现，必须嵌套低级括号怎么办呢？比如{[]}不合法，[]必须嵌套()，即{[()]}合法

发表于 2018-11-14 20:48:53 回复(1)

牛客6739120号

function Stack(){
    var items = [];
    this.push = function(element){
        items.push(element);
    };
    this.pop = function(){
        return items.pop();
    };
    this.size = function(){
        return items.length;
    };
}
function check(str){
    var arr =str.split('');
    var stack= new Stack();
    var aString = '({[]})';
    var index = -1;
    for(var i=0;i<arr.length;i++){
        var item = arr[i];
        if((index = aString.indexOf(item))<3){
            stack.push(item);
        }else{
            var target = stack.pop();
            if(!target){
                return false;
            }
            if(target!==aString.charAt(5-index)){
                return false;
            }
        }
    }
    if(stack.size()){
        return false;
    }else{
    return true;}
}

发表于 2017-07-12 21:36:14 回复(0)

xxj

发表于 2014-12-11 11:35:12 回复(0)

清晨丶_2014

撒飞是撒

发表于 2014-12-04 17:19:42 回复(0)

提交观点

问题信息

栈百度

来自：百度2015安全研发笔试卷

上传者：小小

难度：

8条回答 24收藏 14328浏览

假设有如下字符串： (234453)[234]{2324}

问题信息

热门推荐

相关试题