给定一个表达式A,请返回一个bool值，代表它是否合法。
"[a+b*(5-4)]*{x+b+b*(({1+2}))}" 返回：true
"q*c*k+r-w-{f-e*c+f}" 返回：true
"g+{p+z-v" 返回：false
import java.util.*;
public class ChkExpression {
public boolean chkLegal(String A) {
// write code here
Stack<Character> stack = new Stack<Character>();
HashMap<Character,Character> map = new HashMap<Character,Character>();
map.put('[',']');
map.put('{','}');
map.put('(',')');
for(int i =0;i<A.length();i++){
char ch = A.charAt(i);
if(map.containsKey(ch)){
stack.push(ch);
}else if(map.containsValue(ch)){
if(stack.isEmpty())
return false;
char top = stack.peek();
// if(map.get(top).equals(ch)){
stack.pop();
// }else{
// return false;
//}
}
}
return stack.isEmpty();
}
}
题目也是醉了 测试样例明明就错的
他的意思是左右括号数量相同就ok 头皮发麻
class ChkExpression {
public:
const string dic = "{[(}])";
bool chkLegal(string A) {
stack<int> s;
for(int i = 0; i < A.length(); i++)
if(dic.find(A[i]) != -1){
if(s.empty()) s.push(dic.find(A[i]));
else{
int a = s.top();
if(a < 3 && dic.find(A[i]) >= 3) s.pop();
//if(a + 3 == dic.find(A[i])) s.pop();
else s.push(dic.find(A[i]));
}
}
if(s.empty()) return true;
return false;
}
};
import java.util.*;
public class ChkExpression {
public static boolean chkLegal(String A) {
StringBuffer sb = new StringBuffer(A);
int length = sb.length();
Stack<Character> s = new Stack<Character>();
for (int i = 0; i < length; i++) {
char c = sb.charAt(i);
if (c == '{' || c == '[' || c == '(' ){
s.push(c);
}
if ( c == '}' || c == ']' || c == ')'){
s.pop();
}
}
if(s.isEmpty())
return true;
return false;
}
}
class ChkExpression {
public:
bool chkLegal(string A) {
// write code here
int n=A.length();
int f1=0,f2=0,f3=0;
for(int i=0;i<n;i++)
if(A[i]=='{')
f1++;
else if(A[i]=='}')
f1--;
else if(A[i]=='[')
f2++;
else if(A[i]==']')
f2--;
else if(A[i]=='(')
f3++;
else if(A[i]==')')
f3--;
if(f1==0&&f2==0&&f3==0)
return true;
else
return false;
}
};
//注意看题目给的样子本来就不是严格匹配。题目的样例里{和)也能匹配
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();
}
}
通过测试
class ChkExpression {
public:
bool chkLegal(string A) {
int num=A.size();
int s=0;
int *flag=new int[num];
for(int i=0;i<num;i++)
flag[i]=0;
for(int i=0;i<num;i++)
{
if(A[i]=='{'&&flag[i]==0)
{
flag[i]=1;
s++;
for(int j=i+1;j<num;j++)
if(A[j]=='}'&&flag[j]==0)
{flag[j]=1;s--; break;}
}
if(A[i]=='('&&flag[i]==0)
{
flag[i]=1;
s++;
for(int j=i+1;j<num;j++)
if(A[j]==')'&&flag[j]==0)
{flag[j]=1;s--; break;}
}
if(A[i]=='['&&flag[i]==0)
{
flag[i]=1;
s++;
for(int j=i+1;j<num;j++)
if(A[j]==']'&&flag[j]==0)
{flag[j]=1;s--; break;}
}
}
if(s==0)return true;
else return false;
}
};
# -*- coding:utf-8 -*-
import re
class ChkExpression:
def chkLegal(self, A):
# write code here
try:
A = re.sub('[\[{]', '(', A)
A = re.sub('[\]}]', ')', A)
A = re.sub('[A-Za-z]+', '1', A)
eval(A)
return True
except:
return False 
class ChkExpression {
public:
bool chkLegal(string A) {
stack<char> ch;
for (int i = 0; i < A.length(); i++) {
if (A[i] == '{' || A[i] == '[' || A[i] == '(') {
ch.push(A[i]);
}
if (A[i] == '}' || A[i] == ']' || A[i] == ')') {
if (ch.size() == 0) return false;
ch.pop();
}
}
return ch.size() == 0;
}
};
class ChkExpression {
public:
bool chkLegal(string A) {
stack<char> tmp;
for (int i = 0; i < A.size(); i++)
{
if (A[i] == '{' || A[i] == '[' || A[i] == '(') tmp.push(A[i]);
if (A[i] == '}')
{
if (tmp.empty() || tmp.top() != '{') return false;
tmp.pop();
}
if (A[i] == ']')
{
if (tmp.empty() || tmp.top() != '[') return false;
tmp.pop();
}
if (A[i] == ')')
{
if (tmp.empty() || tmp.top() != '(') return false;
tmp.pop();
}
}
if (tmp.empty()) return true;
return false;
}
};
新思路
package com.special.first;
import java.util.Scanner;
/**
* 去哪儿网01-表达式合法判断
*
* 去哪儿网出的题就这么不严谨把，题目描述的这么少，鬼知道你的意思
* 你所谓的合法有没有包括加减乘除的合法，测试用例都是错的。
*
* 常见的思路就是用栈做，是左括号就进栈，是右括号的不进栈，且弹出栈顶元素
* 这样一对括号就没了，只要判断最后栈的大小为0，说明左右是一一匹配的
* 用真实的栈或者数组模拟都可以
*
* 我这里有一个更新奇的做法，就是计数法
* 1.若是左括号，我就自增，因为中间状态时左括号是可以比右括号多的
* 2.若是右括号，我就自减，同时判断是否小于0，若小于0，说明右括号多了，直接结束了
* 3.遍历结束，最后我判断是否大于0，若大于0，说明左括号多了，正常的合法应该是0
* Create by Special on 2018/3/3 11:03
*/
public class Pro032 {
private static boolean isLeftBucket(char ch){
return ch == '{' || ch == '[' || ch == '(';
}
private static boolean isRightBucket(char ch){
return ch == '}' || ch == ']' || ch == ')';
}
public static boolean chkLegal(String A) {
int status = 0;
boolean result = true;
for(int i = 0; i < A.length(); i++) {
if (isLeftBucket(A.charAt(i))) {
status++;
} else if (isRightBucket(A.charAt(i))) {
status--;
if (status < 0) {
result = false;
break;
}
}
}
return status > 0 ? false : result;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
String str = input.nextLine();
System.out.println(chkLegal(str));
}
}
}
class ChkExpression {
public:
bool chkLegal(string A) {
vector<char> s;
for(int i=0;i<A.size();i++)
{
if(A[i]=='{' || A[i]=='(' || A[i]=='[')
s.push_back(A[i]);
else if(A[i]=='}' || A[i]==')' || A[i]==']')
{
int l = s.size();
if(l < 1)
return false;
else
s.pop_back(); } } if(s.size()>0) return false; return true;
}
};
import java.util.*;
public class ChkExpression {
public boolean chkLegal(String A) {
// write code here
Stack leftOpStack = new Stack();
Stack rightOpStack = new Stack();
for (int i = 0; i < A.length(); i++) {
char curChar = A.charAt(i);
if ("{[(".indexOf(curChar) != -1) {
leftOpStack.push(curChar);
} else if (")]}".indexOf(curChar) != -1) {
rightOpStack.push(curChar);
}
}
return leftOpStack.size() == rightOpStack.size();
}
}
class ChkExpression {//只要左括号和右括号的数量一样就是正确的，真是醉了
public:
bool chkLegal(string A) {
int left=0,right=0;
for(string::size_type idx=0;idx<A.size();++idx){
if('['==A[idx]||'('==A[idx]||'{'==A[idx])
++left;
else if(']'==A[idx]||')'==A[idx]||'}'==A[idx])
++right;
}
if(left==right)
return true;
else
return false;
}
}; 
//jbt
class ChkExpression {
public:
bool chkLegal(string A) {
vector<char> stack;
for(int i=0;i<A.size();i++){
if(A[i] == '{' || A[i] == '[' || A[i] == '(')
stack.push_back(A[i]);
else if(A[i] == '}' || A[i] == ']' || A[i] == ')'){
if(stack.size() == 0)
return false;
else
stack.pop_back();
}
}
if(stack.size() == 0)
return true;
else
return false;
}
};
import java.util.*;
public class ChkExpression {
public boolean chkLegal(String A) {
// 题目意思：让左括号（不管大中小）的数量等于右括号（不管大中小）的数量
// write code here
StringBuilder sb = new StringBuilder(A);
int len = sb.length();
Stack<Character> stack = new Stack<Character>();
for (int i=0; i<len; i++) {
char ch = sb.charAt(i);
if (ch == '(' || ch == '[' || ch == '{')
stack.push(ch);
if (ch == ')' || ch == ']' || ch == '}')
stack.pop();
}
if (stack.isEmpty())
return true;
return false;
}
}
public static boolean chkLegal(String A) {
// write code here
Stack<Character> stack = new Stack<Character>();
char[] cs = A.toCharArray();
for(int i=0;i<cs.length;i++){
if(cs[i] == '(' || cs[i] == '{' || cs[i] == '['){
stack.push(cs[i]);
}
if(cs[i] == ')' || cs[i] == '}' || cs[i] == ']'){
stack.pop();
}
}
return stack.isEmpty();
}
写的挺好的，不能过，改成最简单的就a了,
class ChkExpression {
public:
bool chkLegal(string A) {
// write code here
stack<char> chs;
for (int i = 0; i < A.length(); i++){
char ch = A[i];
if (ch =='{'||ch=='['||ch=='('){
chs.push(ch);
}
else if(ch == '}' || ch == ']' || ch == ')'){
chs.pop();
}
else continue;
}
return chs.empty();
}
};
class ChkExpression {
public:
bool chkLegal(string A) {
stack<char> S;
for(int i=0;i<A.length();i++){
if(A[i]=='{'||A[i]=='['||A[i]=='(')
S.push(A[i]);
else if(A[i]=='}'||A[i]==']'||A[i]==')'){
if(!S.empty())//&&((A[i]=='}'&&S.top()=='{')||(A[i]==']'&&S.top()=='[')||(A[i]==')'&&S.top()=='(')))
S.pop();
else
return false;
}
}
if(!S.empty())
return false;
return true;
}
};
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
