judge.java

一个递归程序 根据数理逻辑中 公式 的递归定义 判断一个表达式是否是公式

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class judge {

	static String str;

	public static boolean isequation(String s) {

		int len, c;
		String sub1, sub2;
		len = s.length();
		
		if (len == 1) // 当字符串长度为1时,仅当它为原子公式时,它才式公式
		{
			if (s.equals("p") == true
					|| s.equals("q") == true
					|| s.equals("r") == true) {
				System.out.println(s);
				return true;
			} else {
				return false;
			}
		} else if (len >= 4) // 公式的长度不能是2和3,因此直接从长度为4的字符串判断
		{
			if ((s.charAt(0) == '(') && (s.charAt(len - 1) == ')')) // 当字符串的第一个符号和最后一个符号为'('和')'时,才有可能是一个公式
			{
				if (s.charAt(1) == '!') // 当第二个符号是否定符号的情况
				{
					sub2 = s.substring(2, len - 1); // 取出字符串的子字符串sub1,递归判断其是否是公式
					if (isequation(sub2)) {
						System.out.println(s);
						return true;
					} else {
						return false;
					}
				} else if (s.charAt(1) == '(') // 当第二个符号是'('符号的情况
				{
					c = find(s, 1, len - 2); // find(string,int,int)用于确定与该'('匹配的')'的位置
					if (c == -1 || c == len - 2 || c == len - 3) { // 匹配括号后，后面必须留出两个字符出来。
						return false;
					} else {
						sub1 = s.substring(1, c+1);
						sub2 = s.substring(c + 2, len - 1);

						if ((s.charAt(c + 1) == '&' || s.charAt(c) == '|')
								&& isequation(sub1) && isequation(sub2)) {
							System.out.println(s);
							return true;
						} else {
							return false;
						}

					}
				} else if (s.charAt(1) == 'p' || s.charAt(1) == 'q'
						|| s.charAt(1) == 'r') // 当第二个符号为原子式时,取余下部
				{ // 分设为sub1,判断sub2是否为公式,
					if (len == 4) {
						return false;// 此种情况必须大于等于5
					} else {
						if (s.charAt(2) == '&' || s.charAt(2) == '|')// 字符串才是公式
						{
							sub1 = s.substring(3, len - 1);
							if (isequation(sub1)) {
								System.out.println(s);
								return true;
							} else {
								return false;
							}
						} else {
							return false;
						}
					}
				} else {
					return false;
				}
			} else {
				return false;
			}// end >=4
		} else {
			return false; // 其他长度的字符串和其他情况的字符串都不是公式
		}
	}

	public static int find(String s, int begin, int end) {
		int n1 = 0, n2 = 0, i = begin;
		while (i <= end) { // 函数find(string,int)用于确定与该'('匹配的')'的位置
			if (s.charAt(i) == '(')
				n1++;
			else if (s.charAt(i) == ')')
				n2++;
			else{
			}
			
			if (n1 == n2)
				break;
			i++;
		}
		if (i > begin && i <= end)
			return i;
		else
			return -1;
	}

	public static void main(String[] args) throws IOException {
		int a;
		BufferedReader sin = new BufferedReader(
				new InputStreamReader(System.in));
		do {
			System.out.println("请输入一个字符串:");
			str = sin.readLine(); // 读入数据,sin即为输入的字符串
			a = str.length();
			if (a == 0)
				System.out.println("该字符串为空，不是一个公式,请重新输入！");
		} while (a == 0);
		System.out.println(str + " 字符串分解如下：");
		if (isequation(str)) {
			System.out.println("\n该字符串是一个公式");
		} else
			System.out.println("\n该字符串不是一个公式");
	}
}