Question

关于JAVA中利用Recursion解决运算问题

Evaluate a reverse polish expression.
假设所有数字都是single digits, 并且都是 intermediate，最后的结果也必须是single digits，并且有+,-,*

例如 "832*-" 的结果是 "2".
"83-2+" 的结果是 "7".
"53-2*11+-" 的结果是 "2".

提示：
主意数字是在一个Srting类里面
使用charAt 和 substring 在 String class

public String evaluate(String expr) {

}

不允许使用loop，只允许使用local variables

想了半天还是不会，谢谢大家了……

Answer 1

import java.io.IOException;
import java.util.Arrays;
import java.util.Stack;

public class Rpn {
public static void main(String args[]) throws IOException {
String s = "83-2+";
Stack<String> tks = new Stack<String>();
tks.addAll(Arrays.asList(s.trim().split("")));
tks.remove("");
try {
int r = evalrpn(tks);
if (!tks.empty())
throw new Exception("error");
System.out.println(r);
} catch (Exception e) {
System.out.println("error");
}
}

private static int evalrpn(Stack<String> tks) throws Exception {
String tk = tks.pop();
int x, y;
try {
x = Integer.parseInt(tk);
} catch (Exception e) {
y = evalrpn(tks);
x = evalrpn(tks);
if (tk.equals("+"))
x += y;
else if (tk.equals("-"))
x -= y;
else if (tk.equals("*"))
x *= y;
else if (tk.equals("/"))
x /= y;
else
throw new Exception();
}
return x;
}
}