62,616
社区成员
发帖
与我相关
我的任务
分享编程解析字符串型的表达式对括号如何处理
我写了一个方法，用于解析字符型的表达式，但是对于括号不知道怎么处理，请高手在我这个程序的基础上改进一下：
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];
}
}
...全文
请发表友善的回复…
发表回复
bigbug9002 2009-08-13
- 打赏
- 举报
上面的程序不能算实数,不能有负数.所以不太好,没有修改.
后来用后缀表达式的方式求值,重写了一个,可以计算负数和实数,其中的数值是用正则提取的.
后来用后缀表达式的方式求值,重写了一个,可以计算负数和实数,其中的数值是用正则提取的.
//本程序可以实现实数的加减乘除四则运算，
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());
}
}bigbug9002 2009-08-13
- 打赏
- 举报
以前写过的一个:
用栈求解.你参考一下?
//本程序只能计算正整数范围内的加减乘除运算。
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());
}
}用栈求解.你参考一下?
bigbug9002 2009-08-13
- 打赏
- 举报
栈外的左括号优先级是最高的。右括号的优先级是最低的。右括号不入栈，遇到右括号时，要一直出栈运算直到左括号。
