求大神解决一个递归笔试题
输入一个类似这样的字符串,"{[()]}" 或者"{[]()}",这样的是合法的; 以下是不合法的"{([])}","{[(])}",求写一个程序验证是否合法.(不可以使用java.util.*) 递归
[解决办法]
忘记了不能用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);
}
}
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];
}
}
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);
}
}
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));
}
}