求一个表达式的算法

Question

String s = "12+8*(2*3*4+5)+456-8/(5/2)";
设计一个好的算法计算该表达式的值
考虑优先级别

Answer 1

简单的就使用Antlr或者JavaCC，而且可以方便扩展。它们都有带表达式计算的Sample

Answer 2

写了一段垃圾代码
    String s = "12+8*(2*3*4+5)+456-8/(5/2)"; 
    String ret = replace(s);
    
    System.out.println(ret);
   
  
  public static String replace(String str){
    String ret = str;
    Pattern p = Pattern.compile("\\((.+?)\\)");
    Matcher m = p.matcher(str);
    while(m.find()){
      String param = calculate(m.group(1));
      ret = ret.replaceFirst("\\("+m.group(1).replaceAll("[*+]", "\\\\$0")+"\\)", param);
      
    }
    if(ret.matches("\\((.+?)\\)")) return replace(ret);
    
    return calculate(ret);
  }
  
  public static String calculate(String str){
//    System.out.println(str);
    String ret = "";
    Pattern p = Pattern.compile("(\\d+(\\.\\d+)?)([/*])(\\d+(\\.\\d+)?)");
    Matcher m = p.matcher(str);
    if(m.find()){
      double pre = new Double(m.group(1)).doubleValue();
      String code = m.group(3);
      double pos = new Double(m.group(4)).doubleValue();
      if("*".equals(code)) ret = pre * pos + "";
      if("/".equals(code)) ret = pre / pos + "";
      return calculate(str.replaceFirst(m.group(0).replaceFirst("\\*", "\\\\*"), ret));
    }else {
      p = Pattern.compile("(\\d+(\\.\\d+)?)([+-])(\\d+(\\.\\d+)?)");
      m = p.matcher(str);
      if(m.find()){
        double pre = new Double(m.group(1)).doubleValue();
        String code = m.group(3);
        double pos = new Double(m.group(4)).doubleValue();
        if("+".equals(code)) ret = pre + pos + "";
        if("-".equals(code)) ret = pre - pos + "";
        return calculate(str.replaceFirst(m.group(0).replaceFirst("\\+", "\\\\+"), ret));
      }
    }
    
    return str;
  }

Answer 3

好像在数据结构中有这么个东西，要两个堆栈，一个A栈放数字，一个B栈放操作符，遇到数字放A,遇到符号放B,同时比较前一个符号，如果现在的符号优先级比栈顶的高，则压栈，否则，提取A栈顶的数字和B栈顶的符号计算后压A栈，流程就这样，其中涉及到符号的优先级，其中最大的两个是),(，别的一样。

Answer 4

javascript有个eval函数可以直接算
java中有没有我就不知道了
你可以用java.util.Stack类,然后自己设计，或者找本数据结构书看看上面应该有算法