正在检查表达式是否为有效公式

Question

递归问题： 公式定义为字符串包含正个位数的数字、变量和运算(例如：+，-，/，*，%(。此外，字符串不包含空格酒吧。两个数字或变量之间的每个运算都是分开的带有括号-"；(("；。

有效的公式为：((6+x(*(4+2((，(((9*4(+(x+8((*(6-5((，6，(3+1(等…

无效公式为：-6，(1+*(x+2(*(1-6((，((6+x((，10，2+x、(33+3(、(1+2(等…

编写一个布尔递归函数，它得到一个字符串"；s"；和如果他是一个有效的公式，则返回true，否则返回false。

• 代码必须通过java编写

---

我的尝试： 我尝试了以下内容，记住"；("小于"("的数目；，然而，这是不对的，因为：；((1+2(("；不是有效的公式。所以我写了以下内容：

public static boolean isFormula(String s) {
return calc(s, 0, 0, 0, 0);
}
public static boolean calc(String s, int oc, int l, int r, int g) {
if (s == "") {
return (oc <= 1 && (l == r));
}
char c = s.charAt(0);
char e = s.charAt(s.length() - 1);
if (g == 0) {
if (!(op(s))) return false;
else {
return calc(s, oc, l, r, g + 1);
}
}
if (c == '(') {
return calc(s.substring(1), oc, l + 1, r, g);
} else if (c == ')') {
return calc(s.substring(1), oc, l, r + 1, g);
} else if ((c >= '0' && c <= '9') || c == 'x') {
if (oc <= 1) {
return calc(s.substring(1), 0, l, r, g);
}
} else if ((c == '+' || c == '-' || c == '*' || c == '/')) {
return calc(s.substring(1), oc + 1, l, r, g);
}
return false;
}
public static boolean op(String s) {
int count = 0;
if (s.charAt(0) == '+' || s.charAt(0) == '-' || s.charAt(0) == '*' || s.charAt(0) == '/') {
count++;
}
String d = s.replace("(", "");
if (d.charAt(0) == '+' || d.charAt(0) == '-' || d.charAt(0) == '*' || d.charAt(0) == '/') {
count++;
}
d = d.replace(")", "");
d = d.replace("+", ",");
d = d.replace("-", ",");
d = d.replace("*", ",");
d = d.replace("/", ",");
String[] words = d.split(",");
int sum = words.length;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '/' || s.charAt(i) == '*') {
count++;
}
}
if (s.contains(" ")) return false;
return (count <= sum - 1);
}

---

想法：我觉得这个问题很复杂，我不知道如何安排代码，因为我的方法似乎不正确，而且很混乱。我很乐意得到一些帮助。我在写这篇文章上下了很大的功夫。非常感谢。

Answer 1

试试这个。

static final Pattern DIGIT_OR_X = Pattern.compile("[\dx]");
static final Pattern OPERATION = Pattern.compile("\([\dx][+*/%-][\dx]\)");
public static boolean isFormula(String s) {
while (true) {
if (DIGIT_OR_X.matcher(s).matches())
return true;
String rep = OPERATION.matcher(s).replaceAll("x");
if (rep.equals(s))
return false;
s = rep;
}
}

测试用例：

assertTrue(isFormula("((6+x)*(4+2))"));
assertTrue(isFormula("(((9*4)+(x+8))*(6-5))"));
assertTrue(isFormula("6"));
assertTrue(isFormula("(3+1)"));
assertFalse(isFormula("-6"));
assertFalse(isFormula("(1+*(x+2)*(1-6))"));
assertFalse(isFormula("( (6+x))"));
assertFalse(isFormula("10"));
assertFalse(isFormula("2+x"));
assertFalse(isFormula("(33+3)"));
assertFalse(isFormula("((1+2))"));

或者也可以不使用正则表达式。

static boolean isFormula(String s) {
return new Object() {
int index = 0;
boolean match(String expects) {
if (index >= s.length() || expects.indexOf(s.charAt(index)) < 0)
return false;
++index;
return true;
}
boolean formula() {
if (match("0123456789x"))
return true;
return match("(")
&& formula() && match("+-*/%") && formula()
&& match(")");
}
boolean parse() {
return formula() && index >= s.length();
}
}.parse();
}