编程解析字符串型的表达式对括号如何处理

Question

我写了一个方法，用于解析字符型的表达式，但是对于括号不知道怎么处理，请高手在我这个程序的基础上改进一下：
package javanumber;import java.util.Stack;public class StringParseTest { /**
 *外层方法：main
 *参数和返回类型 @param args
 *时间：Aug 7, 2009
 *This method is used for:
 *Made by Dimmacro. Call me when you use it by anychance bug happens.
 */
public static void main(String[] args) {
Stack optr=new Stack();
Stack opnd=new Stack();
String opStr="+-*/()";
char[][] opArrays=new char[][]{
{'>','>','<','<','<','>'},
{'>','>','<','<','<','>'},
{'>','>','>','>','<','>'},
{'>','>','>','>','<','>'},
{'<','<','<','<','<',' '},
{'>','>','>','>',' ','>'}

};  //定位符号之间的关系
String expreStr="3+2*3-6/2+2-5*2+2*6-4+5*2"; //表达式
int i=0;
char c=expreStr.charAt(0);
opnd.push(c);  //表达式第一个肯定是数字而不是操作符
while(++i<expreStr.length()){
c=expreStr.charAt(i);
if(opStr.indexOf(String.valueOf(c))==-1){
opnd.push(c);  // 如果是数组压入数组栈
}else{
if(0==optr.size()){
optr.push(c); // 如果之前是空栈，先压入操作符栈
continue;
}
operateRelative(opStr,opArrays,optr,opnd,c);
// if(opStr.indexOf(String.valueOf(c))<4)
optr.push(c);
}
}
System.out.println(opnd+" and "+optr);
int total=getTotal(opArrays,optr,opnd);
System.out.println(total); // 打印算术结果 }
// 按上面循环后可能存在optr里面有操作符，这样的话至少可以保证optr栈的操作符顺序是越上越高的
private static int getTotal(char[][] opArrays, Stack optr, Stack opnd) {
while(!optr.isEmpty()&&!opnd.isEmpty()){
opnd.push(operateMath(opnd.pop(),optr.pop(),opnd.pop()));
}
return (Integer)opnd.peek();
}
// 得到一个操作符后和现optr栈的栈顶进行比较
private static void operateRelative(String opStr, char[][] opArrays, Stack optr,Stack opnd, char c) {
switch(getRelative(opStr,opArrays,(Character)optr.peek(),c)){
case'<': 
return;
case'>':
opnd.push(operateMath(opnd.pop(),optr.pop(),opnd.pop()));
    if(!optr.isEmpty()){
     operateRelative(opStr, opArrays, optr,opnd, c); // 循环比较上一个   
    }
}

}
// 确定操作符和实际计算间的关系
private static int operateMath(Object object, Object object2, Object object3) {
int leftNum=Integer.parseInt(String.valueOf(object));
char opeate=(Character)object2;
int rightNum=Integer.parseInt(String.valueOf(object3));
int result=0;
switch(opeate){
case'+':result=rightNum+leftNum;break;
case'-':result=rightNum-leftNum;break;
case'*':result=rightNum*leftNum;break;
case'/':result=rightNum/leftNum;break;
}
return result;
}
// 取得操作符之间的关系，此关系有二位数组存取
private static char getRelative(String opStr,char[][] opArrays, Character topC, char c) {
int i=opStr.indexOf(String.valueOf(topC));
int k=opStr.indexOf(String.valueOf(c));
return opArrays[i][k];
}}

Answer 1

以前写过的一个:
//本程序只能计算正整数范围内的加减乘除运算。
import java.util.*;public class Expression{
//优先级数组，precede[i][j],表示第i个操作符与第j个操作符的优先级，0，1，2，3，4，5，6分别是'+', '-', '*', '/', '(', ')', '#'
//0表示，第i个操作符优先级小于第j个操作符。1表示大于，2表示相等，3是表示不可能的。
int precede[][]={{1 , 1 , 0 , 0 , 0 , 1 , 1},
                     {1 , 1 , 0 , 0 , 0 , 1 , 1},
                     {1 , 1 , 1 , 1 , 0 , 1 , 1},
                     {1 , 1 , 1 , 1 , 0 , 1 , 1},
                     {0 , 0 , 0 , 0 , 0 , 2 , 3},
                     {1 , 1 , 1 , 1 , 3 , 1 , 1},
                     {0 , 0 , 0 , 0 , 0 , 3 , 2}};
    char[] operate={'+', '-', '*', '/', '(', ')', '#'};
    String exp=null;
    public Expression(String exp){
     this.exp=exp;
    }
int getValueInt(){
Stack<Integer> optr=new Stack<Integer>();
Stack<Integer> opnd=new Stack<Integer>();
String expression=exp+"#";          //给表达式加一个运算符，且是一个结束符
optr.push(6);                     //先把'#'操作符对应的序号入栈。
int index=0;                      //从0开始扫描表达式字符串。
//int sign=1;                       //符号，假设为正
int num=0;
char c=expression.charAt(index++);
while(c!='#'||optr.peek()!=6){
if(indexOperate(c)==-1){
/*if(c=='-'){
sign=-1;
c=expression.charAt(index++);
}else if(c=='+'){
c=expression.charAt(index++);
}*/
while(c>='0'&&c<='9'){
num=num*10+c-'0';
c=expression.charAt(index++);
}
opnd.push(num);
//sign=1;
num=0;
}
if(indexOperate(c)==-1){
System.out.println("Expression is Error!");
System.exit(0);
}
switch(precede[optr.peek()][indexOperate(c)]){
case 0 : 
optr.push(indexOperate(c));
c=expression.charAt(index++);
break;
case 1 :
int num2=opnd.pop();
int opt=optr.pop();
int num1=opnd.pop();
opnd.push(binaryOperation(num1,opt,num2));
break;
case 2 :
optr.pop();
c=expression.charAt(index++);
break;
case 3 :
System.out.println("括号不配对Expression Error!");
System.exit(0);
}//switch
}//while
return opnd.peek();
}
int indexOperate(char c){
for(int i=0;i<operate.length;i++){
if(operate[i]==c) return i;
}
return -1;
}
int binaryOperation(int operand1,int opt,int operand2 ){
switch(opt){
case 0:
return operand1+operand2;
case 1:
return operand1-operand2;
case 2:
return operand1*operand2;
case 3:
return operand1/operand2;
}
return 0;
}
public static void main(String[] args){
Expression e=new Expression("((((2+3)/1)+5)-2)*((9-5)/2+3)");
//Expression e=new Expression("1+5");
System.out.println(e.getValueInt()); }
}
用栈求解.你参考一下?

Answer 2

上面的程序不能算实数,不能有负数.所以不太好,没有修改.后来用后缀表达式的方式求值,重写了一个,可以计算负数和实数,其中的数值是用正则提取的.
//本程序可以实现实数的加减乘除四则运算，
import java.util.*;
import java.util.regex.*;
/**
*
*/
public class Expression{
//优先级数组，precede[i][j],表示第i个操作符与第j个操作符的优先级，0，1，2，3，4，5，6分别是'+', '-', '*', '/', '(', ')', '#'
//0表示，第i个操作符优先级小于第j个操作符。1表示大于，2表示相等，3是表示不可能的。
private int precede[][]={{1 , 1 , 0 , 0 , 0 , 1 , 1},
 {1 , 1 , 0 , 0 , 0 , 1 , 1},
 {1 , 1 , 1 , 1 , 0 , 1 , 1},
 {1 , 1 , 1 , 1 , 0 , 1 , 1},
 {0 , 0 , 0 , 0 , 0 , 2 , 3},
 {1 , 1 , 1 , 1 , 3 , 1 , 1},
 {0 , 0 , 0 , 0 , 0 , 3 , 2}};
    private char[] operator={'+', '-', '*', '/', '(', ')', '#'};
    private String infixExpression=null;
    private ArrayList<MetaData> postfixExpression=new ArrayList<MetaData>();
    public Expression(String exp){
     infixExpression=exp+"#";
    }
    /**定义一个内部类表示表达式中的"元数据",操作数,或者是操作符,只能是两者之一.
     *
     *
    */
    private class MetaData{
     double  dData;    //float operand
     int     iData;    // int operand
     char    operator; //operator
     boolean isOperator=false;
    
     MetaData(double dNum){
     dData=dNum;
     }
     MetaData(int iNum){
     iData=iNum;
     }
     MetaData(char operator){
     this.operator=operator;
     isOperator=true;
     }
     public boolean isOperand(){
     return !isOperator;
     }
     public String toString(){
     if(isOperator){
     return ""+operator;
     }else{
     return ""+dData;
     }
     }
    }//end of inner class MetaData
    
    /**由中缀表达式得到后缀表达式。
    *  设一个堆栈，用来存放操作符，先放一个自定义的操作符’#’，它的优先级是最小的。
    *  扫描整个中缀表达式，操作数直接输出到结果postfixExpression中
    *  如果是操作符，就和堆栈栈顶操作符比较，如果栈顶的优先级高则出栈并输出到结果，直到找到优先小的运算符为止。
    *  如果两者优先级相同，表示是配对的括号，或'#'。
    *  把当前的操作入栈。
    */
private void  getPostfixExp(){
Stack<Integer> optrStack=new Stack<Integer>();   // Integer is a index of operator.
int index=0;                                     // index: index of charachter in infixExpression.
double num=0;                                    //
char c=0;                                        //
optrStack.push(6);                               //'#'  index is 6
//下面的正则用来提取一个数值
//
String regex="([-]?[0-9]+(\\.([0-9]+)?)?)";
Pattern numberPattern=Pattern.compile(regex);
Matcher numberMatcher=numberPattern.matcher(infixExpression);
while(index<infixExpression.length()){
if(numberMatcher.find(index)){
if(numberMatcher.start()==index){
num=Double.parseDouble(numberMatcher.group(1));
postfixExpression.add(new MetaData(num));
index=numberMatcher.end();
}
}
c=infixExpression.charAt(index++);
switch(precede[optrStack.peek()][getOperatorOrder(c)]){    //compare operator in stack with operator in c . get precede.
case 0 :                                              //precede is 0 . means operator'precede in stack small than in c 
optrStack.push(getOperatorOrder(c));
break;
case 1 :
while(precede[optrStack.peek()][getOperatorOrder(c)]==1){
postfixExpression.add(new MetaData(operator[optrStack.pop()]));
}
if(precede[optrStack.peek()][getOperatorOrder(c)]==2){
optrStack.pop();       //pop '('
}else{
optrStack.push(getOperatorOrder(c));
}
break;
case 2 :
optrStack.pop();
break;
case 3 :
System.out.println("括号不配对Expression Error!");
System.exit(0);
}//switch
}//while
}
/*对后缀表达式求值。
* 扫描整个后缀表达式，如果是数值，直接入栈。如果是运算符，出栈两个操作数，运算后，再把结果入栈。
*
*/
public double evaluate(){
getPostfixExp();
Stack<Double> valueStack=new Stack <Double>();
//System.out.println(postfixExpression);
for(MetaData md : postfixExpression){
if(md.isOperand()){
valueStack.push(md.dData);
}else{
double num1=valueStack.pop();
double num2=valueStack.pop();
valueStack.push(binaryOperation(num2,getOperatorOrder(md.operator),num1));
}
//System.out.println(valueStack);
}
return valueStack.pop();
}
/*取得操作符的序号，主要是为了比较优先级时，方便的访问precede这个二维数组。
*/
private int getOperatorOrder(char optr){
 int order;
 switch(optr){
   case '+': order=0; break;
   case '-': order=1; break;
   case '*': order=2; break;
   case '/': order=3; break;
   case '(': order=4; break;
   case ')': order=5; break;
   case '#': order=6; break;
   default : order=-1;
 }
 return order;
}
    /*对两个操作数据进行运算。
    */
private double binaryOperation(double operand1,int opt,double operand2 ){
switch(opt){
case 0:
return operand1+operand2;
case 1:
return operand1-operand2;
case 2:
return operand1*operand2;
case 3:
return operand1/operand2;
}
return 0;
}
public static void main(String[] args){
Expression e=new Expression("((1+-33)*3+(2+2)*5)/-4");
//Expression e=new Expression("1+5");
System.out.println(e.evaluate()); }
}