表达式合法判断

[编程题]表达式合法判断

热度指数：8245 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

写一段代码，判断一个包括'{','[','(',')',']','}'的表达式是否合法(注意看样例的合法规则。)

可以看到一个合法的表达式，左括号和右括号必须相互对应。

请注意：1+(2-[3*1)] 这种表达式是不合法的！

给定一个表达式A,请返回一个bool值，代表它是否合法。

测试样例1：

"[a+b*(5-4)]*{x+b+b*(({1+2}))}"

返回：true

测试样例2：

"q*c*k+r-w-{f-e*c+f}"

返回：true

测试样例3：

"g+{p+z-v"

返回：false

算法知识视频讲解

Java

元公子

public class ChkExpression {
    public boolean chkLegal(String A) {
       Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> map = new HashMap<>(3);
        map.put('[', ']');
        map.put('{', '}');
        map.put('(', ')');
        for (int i = 0; i < A.length(); i++) {
            char ch = A.charAt(i);
            if (ch != '{' && ch != '[' && ch != '(' && ch != '}' && ch != ']' && ch != ')') {
                continue;
            }
            if (map.containsKey(ch)) {
                stack.push(ch);
            } else {
/*                System.out.println(map.get(stack.peek()));
                System.out.println(ch);*/
                if (!stack.empty() && !map.get(stack.pop()).equals(ch)) {
                    return false;
                }
            }
        }
        if (stack.empty()) {
            return true;
        }
        return false;
    }
}

发表于 2022-12-05 14:34:38 回复(0)

Java

Beer201903051701541

嗯，测试用例是个错的，只要两边括号数量相等即可，见了鬼了。。

import java.util.*;

public class ChkExpression {
    public boolean chkLegal(String A) {
        // write code here
        char[] chs = A.toCharArray();
        int count = 0;
       for (char ch : chs) {
           if (ch == '(' || ch == '{' || ch == '[') count++;
           if (ch == ')' || ch == '}' || ch == ']') count--;
       }
        return count == 0;
    }
}

/* 您的代码已保存 答案正确:恭喜！您提交的程序通过了所有的测试用例 */

发表于 2019-08-09 15:02:58 回复(0)

Java

Jimmy-yyj

        	int i = 0;
		for(int j = 0; j < A.length();j++) {
			char c = A.charAt(j);
			if (c=='('||c=='{'||c=='[') {
				i++;
			}else if(c==')'||c=='}'||c==']') {
				i--;
			}
		}
		return i==0;

发表于 2017-03-18 22:45:23 回复(0)

Java

王小叶

//注意看题目给的样子本来就不是严格匹配。题目的样例里{和)也能匹配
import java.util.*;

public class ChkExpression {
    public boolean chkLegal(String A) {
        // write code here
        //凡是遇到右边的括号就将前一个弹出
        ArrayDeque<Character> stack = new ArrayDeque<Character>();
        for(int i=0;i<A.length();i++){
            if(A.charAt(i)=='{' || A.charAt(i)=='[' || A.charAt(i)=='('){
                stack.push(A.charAt(i));
            }else if(A.charAt(i)=='}' || A.charAt(i)==']' || A.charAt(i)==')'){
                if(stack.isEmpty()){
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

发表于 2017-03-06 13:34:36 回复(0)

Java

蛋小圣

char[] s = A.toCharArray();
		Stack<Character> stack = new Stack<Character>(); 
		for(int i=0;i<s.length;i++){
			if(s[i]=='{' || s[i]=='[' || s[i]=='('){
			    stack.push(s[i]);
			}
			if(s[i]=='}' || s[i]==']' || s[i]==')'){	
			    stack.pop();	
			}
		}  System.out.println(stack.empty());

发表于 2016-09-05 16:46:11 回复(0)