200分请教有关公式解析的问题（决不失言）

Question

我这里有个表达式的解析和计算，相信对你有借鉴作用。
//:表达式解析-两栈算法.txt
//:Arithmetic.javapackage citi;
import java.util.Iterator;
import java.util.Stack;
import java.util.ArrayList;public class Arithmetic{
  //定义操作符，为简单起见，只涉及四则运算，可相应扩充之
  static String Operators="+-*/()#";
  //定义操作符的比较优先级，
  //其中1表示前面的操作符优于后面的操作符
  //   -1表示前面的操作符低于后面的操作符  
  //    0表示前面的操作符等于后面的操作符
  //    2表示前面的操作符不可能与后面的操作符相比较，如果碰到，则表达式有错  
  //PrecedeList[0][]表示+和+-*/()#这七个操作符相比较的优先级
  //PrecedeList[1][]表示-和+-*/()#这七个操作符相比较的优先级
  //以此类推
  static byte PrecedeList[][]={
                                { 1, 1,-1,-1,-1, 1, 1},
                                { 1, 1,-1,-1,-1, 1, 1},
                                { 1, 1, 1, 1,-1, 1, 1},
                                { 1, 1, 1, 1,-1, 1, 1},
                                {-1,-1,-1,-1,-1, 0, 2},
                                { 1, 1, 1, 1, 2, 1, 1},
                                {-1,-1,-1,-1,-1, 2, 0}};
  //定义数据中可能出现的数字和小数点，可以扩展
  static String Numbers="0123456789.";
  private Stack Operator,Operand;
  private ArrayList Expression;
  
  public Arithmetic(String inputStr){
   Operator=new Stack();
   Operator.push("#");
   Operand=new Stack();
   Expression=new ArrayList();
   Parse(inputStr);
  }
  //解析输入的表达式，将操作符和数据分开
  //如输入表达式2+3*(32-2)则解析成2 + 3 * ( 32 - 2 )这九个字符串
  private void Parse(String instr){
   String single;  
   int temp;
   String tempstr="#";
   for(int i=0;i<instr.length();i++){  
   single=instr.substring(i,i+1);
   //排除非操作符、数字的非法输入，如2+3m
   //Operators.indexOf(single)==6排除#
   if(Numbers.indexOf(single)<0 && (Operators.indexOf(single)<0 || Operators.indexOf(single)==6)){
   System.out.println("Input have wrong char:"+single);
   Expression.clear();
   return;
   }
   //获得前一个输入字符
   temp=Expression.size()-1;
   if(temp>-1){
   tempstr=(String)Expression.get(temp);
   }
   //排除连续两个操作符的情况，如3**2
   if(Operators.indexOf(single)>-1 && temp>-1 && Operators.indexOf(tempstr)>-1){
   System.out.println("Input have wrong format,two Operators are conjoint");
   Expression.clear();
   return;
   }  
   //如果当前字符是数字（包括.）而且前一字符也是数字，则将当前字符加到前一字符后面
   //其他情况均新添加一个元素
   if(Operators.indexOf(single)<0 && temp>-1 && Operators.indexOf(tempstr)<0){
   Expression.set(temp,tempstr+single);
   }  
   else{
     Expression.add(single);//其他情况均新添加一个元素
   }
   }  
   //为了算法处理方便起见，添加特殊字符＃
   Expression.add("#");   
  }
  
  //比较两个操作符的优先级
  private byte Precede(String firstOperator,String secondOperator){
   return PrecedeList[Operators.indexOf(firstOperator)][Operators.indexOf(secondOperator)];
  }  
  
  //对两个数据字符串进行运算
  private double Operate(String firstOperand,String Operator,String secondOperand){
   if(Operator.equals("+")){
   return (Double.parseDouble(firstOperand)+Double.parseDouble(secondOperand));
   }
   else if(Operator.equals("-")){
   return (Double.parseDouble(firstOperand)-Double.parseDouble(secondOperand));
   }
   else if(Operator.equals("*")){
   return (Double.parseDouble(firstOperand)*Double.parseDouble(secondOperand));
   }
   else if(Operator.equals("/")){
   return (Double.parseDouble(firstOperand)/Double.parseDouble(secondOperand));
   }
   else{
     System.out.println("Operator is wrong!Can throw a Exception");
     return 0;
    }
  }
  //采用两个栈对接解析后的表达式进行运算
  public double Compute(){
   if(Expression.isEmpty()){
   System.out.println("Expresion is empty");
   return 0;
   }
   Iterator it = Expression.iterator();
   String single;
   String firstOperand,secondOperand;
     
   single=(String)it.next();
   while(!(single.equals("#") && Operator.peek().equals("#"))){
   if(Operators.indexOf(single)<0){
   Operand.push(single);single=(String)it.next();
   }
   else{
     switch(Precede((String)Operator.peek(),single)){
      case -1:Operator.push(single);single=(String)it.next();break;
      case 0: Operator.pop();single=(String)it.next();break;
      case 1: 
              secondOperand=(String)Operand.pop();
              firstOperand=(String)Operand.pop();
              Operand.push(String.valueOf(Operate(firstOperand,(String)Operator.pop(),secondOperand)));break;
      case 2: System.out.println("Expression is wrong!Can throw a Exception");break;
     }
     }
   }  
    return Double.parseDouble((String)Operand.pop());
  }
  
  public static void main(String[] args){
   long t1 = System.currentTimeMillis();    
     
   Arithmetic t=new Arithmetic(args[0]);
   System.out.println(t.Compute());  
  
   long t2 = System.currentTimeMillis();
    System.out.println("Time needed: " + (t2 - t1));
  }
}运行：
F:\java>javac Arithmetic.java -d .F:\java>java citi.Arithmetic 3*(34+4*4)
150.0
Time needed: 10

Answer 1

这里是c的 你可以看看他的算法。网址为：http://tzsvc.xiloo.com/ks/datastru/dh3.htm
3.21 
void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new
{
p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号
InitStack(s); //s为运算符栈
while(*p)
{
if(*p是字母)) *q++=*p; //直接输出
else
{
c=gettop(s);
if(*p优先级比c高) push(s,*p);
else
{
while(gettop(s)优先级不比*p低)
{
pop(s,c);*(q++)=c;
}//while
push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则
}//else
}//else
p++;
}//while
}//NiBoLan //参见编译原理教材 
3.22 
int GetValue_NiBoLan(char *str)//对逆波兰式求值
{
p=str;InitStack(s); //s为操作数栈
while(*p)
{
if(*p是数) push(s,*p);
else
{
pop(s,a);pop(s,b);
r=compute(b,*p,a); //假设compute为执行双目运算的过程
push(s,r);
}//else
p++;
}//while
pop(s,r);return r;
}//GetValue_NiBoLan 
3.23 
Status NiBoLan_to_BoLan(char *str,stringtype &new)//把逆波兰表达式str转换为波兰式new
{
p=str;Initstack(s); //s的元素为stringtype类型
while(*p)
{
if(*p为字母) push(s,*p);
else
{
if(StackEmpty(s)) return ERROR;
pop(s,a);
if(StackEmpty(s)) return ERROR;
pop(s,b);
c=link(link(*p,b),a);
push(s,c);
}//else
p++;
}//while
pop(s,new);
if(!StackEmpty(s)) return ERROR;
return OK;
}//NiBoLan_to_BoLan
分析:基本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b). 

Answer 2

其实用beanshell就可以解决了。

Answer 3

把表达式做成树,可惜我的代码都被CIH吃掉了.