求大神解决一个递归笔试题

Question

输入一个类似这样的字符串,"{[()]}" 或者"{[]()}",这样的是合法的; 以下是不合法的"{([])}","{[(])}",求写一个程序验证是否合法.(不可以使用java.util.*)递归

Answer 1

猜测下，“{([])}” 不合法的原因是因为 括号也有 大中小 之分？程序不算太复杂，初步考虑的递归思路就是：
1、向右搜索字符串；
2、发现一个左括号，根据当前层级（大中小）检查是否合法，合法则调用子递归；
3、发现右括号则检查是否跟当前层级匹配，不必配就抛错，匹配就结束本级递归；
4、字符串结束，也结束递归。函数参数定义大概是：
int[本次搜索的结束位置] funCheck(String str, int pos[0～length-1], int type[无大中小])

Answer 2

package csdn;import java.util.HashMap;
import java.util.Map;/**
 * Created by IntelliJ IDEA.
 * User: haoshihai
 * Date: 13-7-22
 * Time: 下午12:03
 * To change this template use File | Settings | File Templates.
 */
public class Tesk {
    static Map<String, Integer> map = new HashMap<String, Integer>();    static {
        map.put("{", 0);
        map.put("}", 1);
        map.put("[", 0);
        map.put("]", 1);
        map.put("(", 0);
        map.put(")", 1);    }    public String check(String str, int status, int level) {
        System.out.println(str);
        if (str.length() == 0) {
            System.out.println("合法");
            return null;
        }
        if(status==1){
            level=level-1;
        }
        String index = str.substring(0, 1);
        String last = str.substring(1);
        int value = getStatus(index);
        int codeLevel = getLevel(index);
        if (status==0&&level>codeLevel) {
            System.out.println("不合法");
        } else {
            check(last, value, codeLevel);//递归调用
        }
        return "null";
    }    public int getStatus(String index) {
        return map.get(index);
    }    public int getLevel(String index) {
        if ("{".equals(index) || "}".equals(index)) {
            return 1;
        }
        if ("[".equals(index) || "]".equals(index)) {
            return 2;
        }
        if ("(".equals(index) || ")".equals(index)) {
            return 3;
        } else {
            return -1;
        }
    }    public static void main(String args[]){
       new Tesk().check("{([])}",0,0);
    }
}

Answer 3

忘记了不能用java.util包
package csdn;/**
 * Created by IntelliJ IDEA.
 * User: haoshihai
 * Date: 13-7-22
 * Time: 下午12:03
 * To change this template use File | Settings | File Templates.
 */
public class Tesk {
    public String check(String str, int status, int level) {
        System.out.println(str);
        if (str.length() == 0) {
            System.out.println("合法");
            return null;
        }
        if(status==1){
            level=level-1;
        }
        String index = str.substring(0, 1);
        String last = str.substring(1);
        int value = getStatus(index);
        int codeLevel = getLevel(index);
        if (status==0&&level>codeLevel) {
            System.out.println("不合法");
        } else {
            check(last, value, codeLevel);//递归调用
        }
        return "null";
    }    public int getStatus(String index) {
        if("{".equals(index) || "[".equals(index)|| "(".equals(index)){
            return 0;
        }
        else{
            return 1;
        }
    }    public int getLevel(String index) {
        if ("{".equals(index) || "}".equals(index)) {
            return 1;
        }
        if ("[".equals(index) || "]".equals(index)) {
            return 2;
        }
        if ("(".equals(index) || ")".equals(index)) {
            return 3;
        } else {
            return -1;
        }
    }    public static void main(String args[]){
       new Tesk().check("{([])}",0,0);
    }
}

Answer 4

不能用java.utils.*，就自己写一个！
public class Test {
  public static void main(final String[] args) {
    String input = "{][[()][]}";
    System.out.println(isValidExp(input));
  }  public static boolean isValidExp(String exp) {
    Stack stack = new Stack(exp.length());
    for (int i = 0; i < exp.length(); i++) {
      char prev = stack.peek();
      char cur = exp.charAt(i);      if (prev == '\0') {
        stack.push(cur);
        continue;
      }      if (mapLevel(prev) + mapLevel(cur) == 0) {
        stack.pop();
        continue;
      }      if (mapLevel(cur) < 0)
        return false;      if (mapLevel(prev) <= mapLevel(cur))
        return false;      stack.push(cur);
    }
    if (stack.peek() != '\0')
      return false;
    return true;
  }  public static int mapLevel(char par) {
    switch (par) {
      case '{':
        return 3;
      case '[':
        return 2;
      case '(':
        return 1;
      case ')':
        return -1;
      case ']':
        return -2;
      case '}':
        return -3;
      default:
        throw new IllegalArgumentException();
    }
  }
}class Stack {
  private char[] iData;  private int iPointer;  public Stack(int size) {
    iData = new char[size];
    iPointer = -1;
  }  public void push(char c) {
    iData[++iPointer] = c;
  }  public char pop() {
    if (iPointer < 0)
      return '\0';
    return iData[iPointer--];
  }  public char peek() {
    if (iPointer < 0)
      return '\0';
    return iData[iPointer];
  }
}

Answer 5

如果同级的括号可以互相包含，就把26行的<=改成<

Answer 6

修改了一下，可以忽略非括号字符
package test;public class Test {
  public static void main(final String[] args) {
    String input = "{[kdfj(ald)][]}";
    System.out.println(isValidExp(input));
  }  public static boolean isValidExp(String exp) {
    Stack stack = new Stack(exp.length());
    for (int i = 0; i < exp.length(); i++) {
      char prev = stack.peek();
      char cur = exp.charAt(i);      if (mapLevel(cur) == 0)
        continue;      if (prev == '\0') {
        stack.push(cur);
        continue;
      }      if (mapLevel(prev) + mapLevel(cur) == 0) {
        stack.pop();
        continue;
      }      if (mapLevel(cur) < 0)
        return false;      if (mapLevel(prev) <= mapLevel(cur))
        return false;      stack.push(cur);
    }
    if (stack.peek() != '\0')
      return false;
    return true;
  }  public static int mapLevel(char par) {
    switch (par) {
      case '{':
        return 3;
      case '[':
        return 2;
      case '(':
        return 1;
      case ')':
        return -1;
      case ']':
        return -2;
      case '}':
        return -3;
      default:
        return 0;
    }
  }
}class Stack {
  private char[] iData;  private int iPointer;  public Stack(int size) {
    iData = new char[size];
    iPointer = -1;
  }  public void push(char c) {
    iData[++iPointer] = c;
  }  public char pop() {
    if (iPointer < 0)
      return '\0';
    return iData[iPointer--];
  }  public char peek() {
    if (iPointer < 0)
      return '\0';
    return iData[iPointer];
  }
}

Answer 7

package csdn;/**
 * Created by IntelliJ IDEA.
 * User: haoshihai
 * Date: 13-7-22
 * Time: 下午12:03
 * To change this template use File | Settings | File Templates.
 */
public class Tesk {
    public String check(String str, String check, int in, int befor_status) {
        System.out.println(check);
        String index = str.substring(in, in + 1);
        int status = getLevel(index);
        if (status < 0) {
            if (befor_status == Math.abs(status) && (in + 1 != str.length())) {
                check = check.substring(0, check.length() - 1);
                status = getLevel(check.substring(check.length() - 1));
                check(str, check, in + 1, status);//递归
            } else if (befor_status == Math.abs(status) && (in + 1 == str.length())) {
                System.out.println("合法");
            } else System.out.println("不合法");
        } else {
            if (status > befor_status) System.out.println("不合法");
            else {
                check = check + index;
                check(str, check, in + 1, status);//递归
            }
        }
        return "null";
    }    public int getLevel(String index) {
        if ("{".equals(index)) {
            return 3;
        } else if ("}".equals(index)) {
            return -3;
        } else if ("[".equals(index)) {
            return 2;
        } else if ("]".equals(index)) {
            return -2;
        } else if ("(".equals(index)) {
            return 1;
        } else if (")".equals(index)) {
            return -1;
        } else {
            return -100;
        }
    }    public static void main(String args[]) {
        new Tesk().check("(]", "", 0, 4);
    }
}

Answer 8

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: -1
at java.lang.String.substring(String.java:1871)
at test.Father.check(Father.java:20)
at test.Father.check(Father.java:32)
at test.Father.main(Father.java:63)输入："()()"

Answer 9

典型的Stack使用。
是左括号就入栈，右括号就与栈顶比较，不匹配就直接返回错误，匹配就弹出栈顶。
输入完时如果栈空则合法，否则是错误的。

Answer 10

package com;/**
 * 这个类实现了最基本的功能，可以判断{.[.(是否有匹配对应的符号。
 * 使用了递归的方式，未引入其它包
 * 但是比如{[{}]}这个功能我还未实现，这个功能其实就是在
 * testall中else if(frist.equals("[")){这一条以及}else if(frist.equals("(")){这一条里面多添加两个判断
 * 得忙工作了，先不写了。
 * 写了如下这些大约花了我一小时，不知道你们需要多长时间。
 * 思路理了2次，第一次的思路错了浪费了好多时间
 */
public class Test {
static boolean flag=true;
//"{[()]}" 或者"{[]()}
//{([])}","{[(])}"
public static void main(String[] args) {
String str="{[()]}{[]}";
System.out.println(test(str)?"正确":"错误");
}

public static boolean test(String str){
//测试是否成对
if(!testdouble(str)) return false;
//测试格式是否正确
testall(str);
return flag;
}

public static void testall(String str){
if(flag==true&&(str.length()!=0)){
String frist = str.substring(0, 1);
if(frist.equals("{")){
int indexOf = str.indexOf("}")+1;
if(indexOf==-1){
flag=false;
}else{
testall(str.substring(1, indexOf-1));
testall(str.substring(indexOf,str.length()));
}
}
else if(frist.equals("[")){
int indexOf = str.indexOf("]")+1;
if(indexOf==-1){
flag=false;
}else{
testall(str.substring(1, indexOf-1));
testall(str.substring(indexOf,str.length()));
}
}else if(frist.equals("(")){
int indexOf = str.indexOf(")")+1;
if(indexOf==-1){
flag=false;
}else{
testall(str.substring(1, indexOf-1));
testall(str.substring(indexOf,str.length()));
}
}else{
testall(str.substring(1));
}
}
}
//做测试，看数量'{'、'}'等是否相同，不相同的话直接返回false
public static boolean testdouble(String str){
int bignumleft=0;
int bignumright=0;
int cennumleft=0;
int cennumright=0;
int litnumleft=0;
int litnumright=0;
char[] ch=str.toCharArray();
for(char c:ch){
switch (c) {
case '{':
bignumleft++;
break;
case '}':
bignumright++;
break;
case '[':
cennumleft++;
break;
case ']':
cennumright++;
break;
case '(':
litnumleft++;
break;
case ')':
litnumright++;
break;
default:
break;
}
}
return !((bignumleft!=bignumright)||(cennumleft!=cennumright)||(litnumleft!=litnumright));
}
}

Answer 11

栈，你懂？你从左到右扫描输入，只有可能出现左括号或者右括号。那么就让左括号入栈。
括号的性质是左右匹配，那么，栈里只有左括号。当你碰到一个右括号的时候，它一定和你栈顶（也就是你扫描字串时最后见到的那个匹配），比如 { [ () () ] [] }
栈尾到栈顶依次是{ [ (，当你看到了)，它一定和栈顶的(匹配，否则就是不合法的。匹配之后，那个左括号就应该出栈，因为它已经跟右括号OOXX去了，然后你再往后看，又一个左括号接一个右括号，让他们继续OOXX，剩下的就是] [] }，而你栈里是{ [。
明白了这个规律就简单了
如果你见到右括号，你就跟栈顶的匹配。如果你见到左括号，它一定是级别低于之前栈顶的左括号，否则就是错的。

Answer 12

栈，你懂？你从左到右扫描输入，只有可能出现左括号或者右括号。那么就让左括号入栈。
括号的性质是左右匹配，那么，栈里只有左括号。当你碰到一个右括号的时候，它一定和你栈顶（也就是你扫描字串时最后见到的那个匹配），比如 { [ () () ] [] }
栈尾到栈顶依次是{ [ (，当你看到了)，它一定和栈顶的(匹配，否则就是不合法的。匹配之后，那个左括号就应该出栈，因为它已经跟右括号OOXX去了，然后你再往后看，又一个左括号接一个右括号，让他们继续OOXX，剩下的就是] [] }，而你栈里是{ [。
明白了这个规律就简单了
如果你见到右括号，你就跟栈顶的匹配。如果你见到左括号，它一定是级别低于之前栈顶的左括号，否则就是错的。
有道理，我写的东西逻辑不严谨，没有怎么测试。

Answer 13

算了，最终还是做完了吧。。
上面我写的那个也是有bug的。
下面的这个欢迎测试，有问题引用一下。。package com;/**
 * 这个类实现了功能,欢迎测试找bug
 */
public class Test {
static boolean flag=true;
//"{[()]}" 或者"{[]()}
//{([])}","{[(])}"
public static void main(String[] args) {
String str="{[()]}{[]}()(){()[]}";
System.out.println(test(str)?"正确":"错误");
}

public static boolean test(String str){
//测试是否成对
if(!testdouble(str)) return false;
//测试格式是否正确
testall(str);
return flag;
}

public static void testall(String str){
if(flag==true&&(str.length()!=0)){
String frist = str.substring(0, 1);
if(frist.equals("{")){
int indexOf = str.indexOf("}")+1;
if(indexOf==0){
flag=false;
}else{
testall(str.substring(1, indexOf-1));
testall(str.substring(indexOf,str.length()));
}
}
else if(frist.equals("[")){
int indexOf = str.indexOf("]")+1;
if(indexOf==0){
flag=false;
}else{
String twostr=str.substring(1, indexOf-1);
if(twostr.contains("{"))flag=false;
testall(twostr);
testall(str.substring(indexOf,str.length()));
}
}else if(frist.equals("(")){
int indexOf = str.indexOf(")")+1;

if(indexOf==0){
flag=false;
}else{
String threestr=str.substring(1, indexOf-1);
if(threestr.contains("{")||threestr.contains("["))flag=false;
testall(threestr);
testall(str.substring(indexOf,str.length()));
}
}else{
testall(str.substring(1));
}
}
}
//做测试，看数量'{'、'}'等是否相同，不相同的话直接返回false
public static boolean testdouble(String str){
int bignumleft=0;
int bignumright=0;
int cennumleft=0;
int cennumright=0;
int litnumleft=0;
int litnumright=0;
char[] ch=str.toCharArray();
for(char c:ch){
switch (c) {
case '{':
bignumleft++;
break;
case '}':
bignumright++;
break;
case '[':
cennumleft++;
break;
case ']':
cennumright++;
break;
case '(':
litnumleft++;
break;
case ')':
litnumright++;
break;
default:
break;
}
}
return !((bignumleft!=bignumright)||(cennumleft!=cennumright)||(litnumleft!=litnumright));
}
}

Answer 14

试一下：
String input = "{[()]}[])(";

Answer 15

试一下：
String input = "{[()]}[])(";
刚刚想贴fix出来的。。想想算了木有人会注意到。既然注意到了。。
public class Test2 {  public static void main(final String[] args) {
    String input = "{[()]}[])(";
    System.out.println(isValidExp(input));
  }  public static boolean isValidExp(String exp) {
    Stack stack = new Stack(exp.length());
    for (int i = 0; i < exp.length(); i++) {
      char prev = stack.peek();
      char cur = exp.charAt(i);      if (mapLevel(cur) == 0)
        continue;      if (prev == '\0') {
        if (mapLevel(cur) < 0)
          return false;        stack.push(cur);
        continue;
      }      if (mapLevel(prev) + mapLevel(cur) == 0) {
        stack.pop();
        continue;
      }      if (mapLevel(cur) < 0)
        return false;      if (mapLevel(prev) <= mapLevel(cur))
        return false;      stack.push(cur);
    }
    if (stack.peek() != '\0')
      return false;
    return true;
  }  public static int mapLevel(char par) {
    switch (par) {
      case '{':
        return 3;
      case '[':
        return 2;
      case '(':
        return 1;
      case ')':
        return -1;
      case ']':
        return -2;
      case '}':
        return -3;
      default:
        return 0;
    }
  }
}class Stack {
  private char[] iData;  private int iPointer;  public Stack(int size) {
    iData = new char[size];
    iPointer = -1;
  }  public void push(char c) {
    iData[++iPointer] = c;
  }  public char pop() {
    if (iPointer < 0)
      return '\0';
    return iData[iPointer--];
  }  public char peek() {
    if (iPointer < 0)
      return '\0';
    return iData[iPointer];
  }
}