class Node<E>{ //o:object public E o; //p:priority public int p; //l:left,r:right public Node l,r;
public Node(E o){ this.o = o; } }class Stack<E>{ private Node cur; private int size = 0;
public void push(E o){ Node<E> n = new Node<E>(o); if(cur!=null){ cur.r = n; n.l = cur; } cur = n; size++; }
public E pop(){ if(size==0) return null; try{ size--; return (E)cur.o; }finally{ cur = cur.l; if(cur!=null) cur.r = null; } }
public int size(){ return size; } }class Tree{ private Node<String> cur,root,start; private Stack<Node> nodes; private String s[],result;
public void insert(String s[]){
if(s.length<=2) return; int x = Parser.X_INIT; nodes = new Stack<Node>();
//create a root in order to get a start //and solve the condition of starting with "(" cur = new Node<String>(Parser.operators[0]); cur.l = new Node<String>("0"); cur.p = Parser.p(Parser.operators[0])+x; root = cur; start = root;
for(int i=0;i<s.length;i++){ //a new node Node<String> n = new Node<String>(s[i]);
//while s is () , increase or decrease its priority x += s[i].equals("(")?Parser.X_STEP:s[i].equals(")")?-Parser.X_STEP:0;
if(Parser.isOperator(s[i])){
n.p = Parser.p(s[i])+x;
//while this node's priority is less than the previous' //then roll back while(cur.p>n.p) rollBack();
//while this node's priority is bigger than the previous' //then connect this to the right child //and move the origin right child to its left child if(cur.p<n.p){ nodes.push(cur); n.l = cur.r; cur.r = n;
//while this node's priority is the same as the previous' //then connect its left child with the previous' //and move the parent connect from the previous' to this }else if(cur.p==n.p){ n.l = cur; if(nodes.size()==0) root = n; }
cur = n;
//while this node is a number //then connect it to the current node's right child }else if(java.util.regex.Pattern.matches("(\\d+\\.\\d+)|\\d+",s[i])){ cur.r = n; } }
//rollback at end while(nodes.size()>0) rollBack();
//remove the temp start: //find the node which left child is the temp start //then connect its left child to the temp start's right child if(start==root){ root = start.r; }else{ cur = root; while(cur.l.l.l!=null) cur = cur.l; cur.l = cur.l.r; }
}
//roll back to the parent tree private void rollBack(){ Node<String> temp = nodes.pop(); temp.r = cur; cur = temp; if(nodes.size()==0) root = temp; }
//iterate the tree prefixally public String prefix(){ result = ""; prefixIterate(root); return result; } private void prefixIterate(Node n){ if(n==null) return; result += n.o+" "; prefixIterate(n.l); prefixIterate(n.r); } //iterate the tree postfixally public String postfix(){ result = ""; postfixIterate(root); return result; } private void postfixIterate(Node n){ if(n==null) return; postfixIterate(n.l); postfixIterate(n.r); result += n.o+" "; } }class Calculator{
//get the result from postfix expression public static double calculateInPostfix(String s[]){ Stack<Double> num = new Stack<Double>(); double result = 0; for(int i=0;i<s.length;i++) if(Parser.isOperator(s[i])){ double d1 = num.pop(); double d2 = num.pop(); result = calculate(d1,d2,s[i]); num.push(result); }else{ num.push(Double.parseDouble(s[i])); } return num.pop(); }
//the calculate rule //you can add your rule here <<<<<<<<<<<<<<<<<<<<<<< public static double calculate(double d1,double d2,String operator){ double result = 0; if(operator.equals("+")){ result = d2+d1; }else if(operator.equals("-")){ result = d2-d1; }else if(operator.equals("*")){ result = d2*d1; }else if(operator.equals("/")){ result = d2/d1; }else if(operator.equals("^")){ result = Math.pow(d2,d1); }else if(operator.equals("#")){ result = Math.pow(d2,1/d1); } return result; } }public class Parser{
//the support operators public static final String operators[] = new String[]{"+","-","*","/","^","#"}; //the support operators in regex public static final String operators2[] = new String[]{"\\+","\\-","\\*","\\/","\\^","\\#"}; //the prioritie of the operators //it should be less than X_STEP public static final int priorities[] = new int[]{2,2,4,4,6,6}; //you can add your operator in upwards 3 arrays <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
//x:extension priority //the extension priority of () //X_INIT is the initial value //and the X_STEP is the extension priority; public static int X_INIT = 1,X_STEP = 10;
private String s[]; private Tree t = new Tree();
public Parser(String s){ this.s = parseSource(s); t.insert(this.s); }
//judge if it is an operator public static boolean isOperator(String s){ for(int i=0;i<operators.length;i++) if(operators[i].equals(s)) return true; return false; }
//get the priority fo operator public static int p(String s){ for(int i=0;i<operators.length;i++) if(operators[i].equals(s)) return priorities[i]; return -1; }
//hanle the source string private String[] parseSource(String s){ String rule = "[^\\d|\\(|\\)|\\."; for(int i=0;i<operators2.length;i++) rule += "|"+operators2[i]; rule += "]"; s = s.trim().replaceAll(rule,""); for(int i=0;i<operators2.length;i++) s = s.replaceAll(operators2[i]," "+operators2[i]+" "); s = s.replaceAll("\\(","( ").replaceAll("\\)"," )"); return s.split(" +"); } public double calculate(){ return Calculator.calculateInPostfix(t.postfix().split(" ")); }
//get the infix expression public String converToInfix(){ String result = ""; for(int i=0;i<s.length;i++) result += s[i]+" "; return result; }
//get the prefix expression public String converToPrefix(){ return t.prefix(); }
//get the postfix expression public String converToPostfix(){ return t.postfix(); }
public static void main(String args[]){ Parser p = new Parser("2438-(245+722)/24-25*12/12*2-452-24/24.6"); //test System.out.println("中缀表达式:"+p.converToInfix()); System.out.println("前缀表达式:"+p.converToPrefix()); System.out.println("后缀表达式:"+p.converToPostfix()); System.out.println("计算结果: "+p.calculate()); } } 栈的话一般书上都有说,这个偶以前用二叉树做的,顶住档先吧
2 可以扔给数据库做,或者用BigInteger
class Node<E>{ //o:object
public E o;
//p:priority
public int p;
//l:left,r:right
public Node l,r;
public Node(E o){
this.o = o;
}
}class Stack<E>{ private Node cur;
private int size = 0;
public void push(E o){
Node<E> n = new Node<E>(o);
if(cur!=null){
cur.r = n;
n.l = cur;
}
cur = n;
size++;
}
public E pop(){
if(size==0)
return null;
try{
size--;
return (E)cur.o;
}finally{
cur = cur.l;
if(cur!=null)
cur.r = null;
}
}
public int size(){
return size;
}
}class Tree{ private Node<String> cur,root,start;
private Stack<Node> nodes;
private String s[],result;
public void insert(String s[]){
if(s.length<=2)
return;
int x = Parser.X_INIT;
nodes = new Stack<Node>();
//create a root in order to get a start
//and solve the condition of starting with "("
cur = new Node<String>(Parser.operators[0]);
cur.l = new Node<String>("0");
cur.p = Parser.p(Parser.operators[0])+x;
root = cur;
start = root;
for(int i=0;i<s.length;i++){ //a new node
Node<String> n = new Node<String>(s[i]);
//while s is () , increase or decrease its priority
x += s[i].equals("(")?Parser.X_STEP:s[i].equals(")")?-Parser.X_STEP:0;
if(Parser.isOperator(s[i])){
n.p = Parser.p(s[i])+x;
//while this node's priority is less than the previous'
//then roll back
while(cur.p>n.p)
rollBack();
//while this node's priority is bigger than the previous'
//then connect this to the right child
//and move the origin right child to its left child
if(cur.p<n.p){
nodes.push(cur);
n.l = cur.r;
cur.r = n;
//while this node's priority is the same as the previous'
//then connect its left child with the previous'
//and move the parent connect from the previous' to this
}else if(cur.p==n.p){
n.l = cur;
if(nodes.size()==0)
root = n;
}
cur = n;
//while this node is a number
//then connect it to the current node's right child
}else if(java.util.regex.Pattern.matches("(\\d+\\.\\d+)|\\d+",s[i])){
cur.r = n;
}
}
//rollback at end
while(nodes.size()>0)
rollBack();
//remove the temp start:
//find the node which left child is the temp start
//then connect its left child to the temp start's right child
if(start==root){
root = start.r;
}else{
cur = root;
while(cur.l.l.l!=null)
cur = cur.l;
cur.l = cur.l.r;
}
}
//roll back to the parent tree
private void rollBack(){
Node<String> temp = nodes.pop();
temp.r = cur;
cur = temp;
if(nodes.size()==0)
root = temp;
}
//iterate the tree prefixally
public String prefix(){
result = "";
prefixIterate(root);
return result;
}
private void prefixIterate(Node n){
if(n==null)
return;
result += n.o+" ";
prefixIterate(n.l);
prefixIterate(n.r);
} //iterate the tree postfixally
public String postfix(){
result = "";
postfixIterate(root);
return result;
}
private void postfixIterate(Node n){
if(n==null)
return;
postfixIterate(n.l);
postfixIterate(n.r);
result += n.o+" ";
}
}class Calculator{
//get the result from postfix expression
public static double calculateInPostfix(String s[]){
Stack<Double> num = new Stack<Double>();
double result = 0;
for(int i=0;i<s.length;i++)
if(Parser.isOperator(s[i])){
double d1 = num.pop();
double d2 = num.pop();
result = calculate(d1,d2,s[i]);
num.push(result);
}else{
num.push(Double.parseDouble(s[i]));
}
return num.pop();
}
//the calculate rule
//you can add your rule here <<<<<<<<<<<<<<<<<<<<<<<
public static double calculate(double d1,double d2,String operator){
double result = 0;
if(operator.equals("+")){
result = d2+d1;
}else if(operator.equals("-")){
result = d2-d1;
}else if(operator.equals("*")){
result = d2*d1;
}else if(operator.equals("/")){
result = d2/d1;
}else if(operator.equals("^")){
result = Math.pow(d2,d1);
}else if(operator.equals("#")){
result = Math.pow(d2,1/d1);
}
return result;
}
}public class Parser{
//the support operators
public static final String operators[] = new String[]{"+","-","*","/","^","#"};
//the support operators in regex
public static final String operators2[] = new String[]{"\\+","\\-","\\*","\\/","\\^","\\#"};
//the prioritie of the operators
//it should be less than X_STEP
public static final int priorities[] = new int[]{2,2,4,4,6,6};
//you can add your operator in upwards 3 arrays <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
//x:extension priority
//the extension priority of ()
//X_INIT is the initial value
//and the X_STEP is the extension priority;
public static int X_INIT = 1,X_STEP = 10;
private String s[];
private Tree t = new Tree();
public Parser(String s){
this.s = parseSource(s);
t.insert(this.s);
}
//judge if it is an operator
public static boolean isOperator(String s){
for(int i=0;i<operators.length;i++)
if(operators[i].equals(s))
return true;
return false;
}
//get the priority fo operator
public static int p(String s){
for(int i=0;i<operators.length;i++)
if(operators[i].equals(s))
return priorities[i];
return -1;
}
//hanle the source string
private String[] parseSource(String s){
String rule = "[^\\d|\\(|\\)|\\.";
for(int i=0;i<operators2.length;i++)
rule += "|"+operators2[i];
rule += "]";
s = s.trim().replaceAll(rule,"");
for(int i=0;i<operators2.length;i++)
s = s.replaceAll(operators2[i]," "+operators2[i]+" ");
s = s.replaceAll("\\(","( ").replaceAll("\\)"," )");
return s.split(" +");
} public double calculate(){
return Calculator.calculateInPostfix(t.postfix().split(" "));
}
//get the infix expression
public String converToInfix(){
String result = "";
for(int i=0;i<s.length;i++)
result += s[i]+" ";
return result;
}
//get the prefix expression
public String converToPrefix(){
return t.prefix();
}
//get the postfix expression
public String converToPostfix(){
return t.postfix();
}
public static void main(String args[]){
Parser p = new Parser("2438-(245+722)/24-25*12/12*2-452-24/24.6"); //test
System.out.println("中缀表达式:"+p.converToInfix());
System.out.println("前缀表达式:"+p.converToPrefix());
System.out.println("后缀表达式:"+p.converToPostfix());
System.out.println("计算结果: "+p.calculate());
}
}
栈的话一般书上都有说,这个偶以前用二叉树做的,顶住档先吧
他就像javascript中的EVAL似的.可以把字符串写的表达式,算出值来.
最适合你说的这种情况
MVEL.eval("1+2*3*(5+6)"); 就能算出值了
BigInteger b2 = new BigInteger("923948723894723947230598");
BigInteger b3 = b1.add(b2);
System.out.println(b3.toString());
对超过double值范围的或者说:高精度(或任意精度)的表达式求值问题,请楼主使用著名的JEP包吧(JAVA表达式求值包,功能很强大!)
如:楼主的例子(引申一下,变得更复杂些):
234535098234095890234589038.9999999998888888888888888888888888888888*(923948723894723947230598.7777777777777777+12.00999999999999999999999999999999999999999999999999)
值为:
2.166984047219166216979260416663208E+50(精度我设定的是:MathContext.DECIMAL128)使用的参考代码:(总共三步)Jep jep = new Jep(new BigDecComponents(MathContext.DECIMAL128));//生成指定计算精度的jep对象
Object rs=jep.evaluate(
jep.parse("234535098234095890234589038.9999999998888888888888888888888888888888*(923948723894723947230598.7777777777777777+12.00999999999999999999999999999999999999999999999999)"
));//对指定的任意表达式进行求值
System.out.println(rs);//打印表达式的值