任意字符串转换成数学表达式

还好我宝刀未老,嘿嘿,您要的这个程序,连写带测试,用了3个多小时(别说我菜,毕竟我是专门为了你工作3个多小时啊)。 事先声明,这玩意不好整,若您只是一时起兴,那么看看代码就可以了,若您是真想研究,那么不懂的地方可以私聊我。 您说的题目,就是数据结构里的“表达式求值”问题。 问题:给出一个表达式,其内包含(、)、+、-、*、/、%等运算符,要求写出程序,计算出表达式的值。 其实,这个问题主要就是练习程序员对“栈”的使用。只要理解了原理,代码还是很好写的。 背景: 咱们常见的表达式是“中缀式”,其实,还有“前缀式”和“后缀式”的概念(具体的介绍请您自己去百度)。 如,中缀式“4+5”,转换成后缀式为“45+” 。所谓的前缀、后缀、中缀指的就是运算符号的位置,在两个操作数的哪一边。 一般,都会将中缀式转换为后缀式后,再计算表达式的值。 但是,我个人觉得这样很麻烦,所以,就一气呵成,直接在解析中缀式的同时,计算表达式的值。 咱们先说说对中缀表达式求值的原理是什么: 表达式的运算规则: |-  优先级高的运算符先计算。 |-  优先级相同的运算符一般按照运算符的运算结合顺序计算。 |-  若有括号,则从最内层括号开始计算。 表达式求值都需要2个栈。一个是符号栈,另一个是数字栈。 拿上面的后缀式45+ 来说, 咱们刚才将表达式从4+5转换到45+的过程是咱们一眼就能看出来的,但是计算机不能像咱们这样做,因为他不会。他只会从表达式的开头,顺序扫描表达式的每一个字符,它不能像咱们一样 一眼就‘看’出来。 计算机是如何转换的呢? 1.从左到右顺序扫描表达式的每一个字符。 2.如果是操作数 则直接压入数字栈。 3.如果是操作符 则根据符号栈的当前状态来决定怎么处理这个符号。 处理运算符的过程: |-  如果当前符号栈为空,则直接将该运算符压入符号栈。 |-  如果当前符号栈栈顶符号是左括号‘(’则也直接将该运算符压入符号栈。 |-  如果当前符号栈栈顶符号的优先级<该运算符,还是直接将该运算符压栈。 |-  如果当前符号栈栈顶符号的优先级>=该运算符,则将栈顶运算符(OP)取出来,接着从数字栈中取2个数b、a,然后将a(OP)b的结果压入数字栈中。 |-  如果当前符号是右括号‘)’,则不将它压入栈,而是不断从2个栈中,弹出1个符号和2个操作数,然后将运算结果压入数字栈 ,直到遇到左括号‘(’。 |-  然后继续向表达式的后面扫描,直到表达式结束。 当表达式解析结束的时候,若符号栈不为空,则不断的从符号栈和数字栈中弹出元素,进行计算。 当符号栈为空后,数字栈栈顶元素就是最后的结果。 理论结束了,咱们的程序由3个类组成: |-  一个栈(Stack)类。 |-  一个表达式解析(ExpressionParser)类。 用于解析表达式。 |-  一个Test类。其内定义了main方法。 范例1:Stack类。[code=java]package org.cxy.expression; import java.util.*; public class Stack<T> {         private ArrayList<T> stack;         /**          *   功能:初始化堆栈。          * */         public Stack(){                 this.stack = new ArrayList<T>();         }                 /**          *   功能:查看栈顶元素。          * */         public T peek(){                 return this.stack.size()>0?this.stack.get(this.stack.size()-1):null;         }                 /**          *   功能:将元素压栈。          * */         public boolean push(T e){                 boolean mark = false;                 if(e != null){                         this.stack.add(e);                         mark = true;                 }                 return mark;         }                 /**          *   功能:将栈顶元素弹栈。          * */         public T pop(){                 T e = null;                 if(this.stack.size()>0){                         e = this.stack.remove(this.stack.size()-1);                 }                 return e;         }                 /**          *   功能:判断栈是否为空。          * */         public boolean isEmpty(){                 return this.stack.size() == 0 ;         }                 /**          *   功能:返回栈内元素的个数。          * */         public int size(){                 return this.stack.size();         }         public String toString(){                 StringBuffer sub = new StringBuffer();                 sub.append("{");                 for(int i=0;i<this.stack.size();i++){                         sub.append(this.stack.get(i));                         sub.append(",");                 }                 sub.append("}");                 return sub.toString();         } }[/code]范例2:ExpressionParser类。[code=java]package org.cxy.expression; public class ExpressionParser {         private Stack<Character> chStack; // 创建一个符号栈。         private Stack<Double> numStack; // 创建一个数字栈。         private StringBuffer expression;         /**          * 功能:初始化表达式。          */         public ExpressionParser(String expression) {                 this.expression = new StringBuffer(expression);                 this.chStack = new Stack<Character>();                 this.numStack = new Stack<Double>();         }         /**          * 功能:计算表达式的值。          */         public double parse() throws Exception {                 // 若表达式还没有解析完。                 while (this.expression.length() > 0) {                         // 获取当前表达式头部的第一个字符。                         char ch = this.expression.charAt(0);                         this.expression.deleteCharAt(0);                         double num = 0;                         boolean existNum = false;                         // 若当前读取到的是数字。                         while (ch >= '0' && ch <= '9') {                                 num = num * 10 + ch - '0';                                 existNum = true;                                 if (this.expression.length() > 0) {                                         ch = this.expression.charAt(0);                                         this.expression.deleteCharAt(0);                                 } else {                                         break;                                 }                         }                         // 若刚刚解析完一个数字,则将数字压栈。                         if (existNum) {                                 this.numStack.push(num);                                 //若整个表达式的解析已经结束了。                                 if(this.expression.length() == 0 && ch >= '0' && ch <= '9'){                                         break;                                 }                         }                         // 若符号栈为空 或 栈顶元素为左括号 或 ch本身就是左括号,则直接将符号压入栈。                         if (this.chStack.isEmpty() || this.chStack.peek() == '(' || ch == '(') {                                 this.chStack.push(ch);                                 continue;                         }                         switch (ch) {                                 case ')': {// 若当前符号是右括号,则不断的弹出一个运算符和两个操作数,直到遇到左括号为止。                                         while (this.numStack.size() >= 2 && !this.chStack.isEmpty() && this.chStack.peek() != '(') {                                                 this.calc();                                         }                                         if (!this.chStack.isEmpty() && this.chStack.peek() == '(') {                                                 this.chStack.pop(); // 弹出这个左括号。                                                 continue;                                         } else {                                                 throw new IllegalArgumentException("括号的数量不匹配!");                                         }                                 }                                 case '*':                                 case '/':                                 case '%': {                                         // 若符号栈栈顶元素为+、-、( 或者符号栈为空,则意味着符号栈栈顶符号比ch优先级底,所以,将ch压栈。否则,将符号栈栈顶元素弹出来,然后开始计算。                                         while (this.numStack.size() >= 2 && !(this.chStack.isEmpty() || this.chStack.peek() == '(' || this.chStack.peek() == '+' || this.chStack.peek() == '-')) {                                                 this.calc();                                         }                                         // 若符号栈栈顶元素优先级比ch的低。                                         if (this.chStack.isEmpty() || this.chStack.peek() == '(' || this.chStack.peek() == '+' || this.chStack.peek() == '-') {                                                 this.chStack.push(ch);                                                 continue;                                         }                                 }                                 case '+':                                 case '-':{                                         // 若当前符号栈栈顶元素不是(,符号栈也不为空,则将符号栈栈顶元素弹出来,然后开始计算。因为+、-号的优先级最低。                                         while (this.numStack.size() >= 2 && (!this.chStack.isEmpty() || this.chStack.peek() != '(')) {                                                 this.calc();                                         }                                         if (this.chStack.isEmpty() || this.chStack.peek() == '(') {                                                 // 若符号栈栈顶元素为(、或符号栈为空,则将ch压栈。                                                 this.chStack.push(ch);                                                 continue;                                         } else {                                                 throw new IllegalArgumentException("表达式格式不合法!");                                         }                                 }                                 default : throw new IllegalArgumentException("运算符非法!");                         }// switch 结束。                 }// while 结束。                 // 若符号栈不为空,则不断的从符号栈和数字栈中弹出元素,进行计算。                 while(!this.chStack.isEmpty()){                         this.calc();                 }                 // 若最终数字栈中仅存一个元素,则证明表达式正确,栈顶元素就是表达式的值。                 return this.numStack.size() == 1 ? this.numStack.pop() : null;         }         /**          * 功能:依据指定的操作数、运算符,进行运算。          */         private void calc() throws Exception {                 double b = this.numStack.pop();                 double a = this.numStack.pop();                 char op = this.chStack.pop();                 double result = 0;                 switch (op) {                         case '+':        result = a + b;        break;                         case '-':        result = a - b;        break;                         case '*':        result = a * b;        break;                         case '/': {                                 if (b == 0) {                                         throw new ArithmeticException("除数不能为0!");                                 }                                 result = a / b;                                 break;                         }                         case '%': {                                 if (b == 0) {                                         throw new ArithmeticException("除数不能为0!");                                 }                                 result = a % b;                                 break;                         }                 }                 // 将运算的结果压栈。                 this.numStack.push(result);                        }         public void print(){                 System.out.println("数字栈元素:"+this.numStack);                 System.out.println("符号栈元素:"+this.chStack);         } }[/code]范例3:Test类。[code=java]package org.cxy.expression; public class Test {         public static void main(String[] args){ //                String e = "65+403";    //                String e = "65+403*4-125/25%4/3+4"; //                String e = "65+403*4)"; //                String e = "(65+403)*4-125/(25%4)/3+4"; //                String e = "((65+403)*4-125)/0/3+4";                 String e = "((65+403)*4-125/(25%4))/3+4";                 ExpressionParser ep = new ExpressionParser(e);                 try {                         System.out.print("表达式 "+e+" 计算结果为:"+ep.parse());                 } catch (Exception e1) {                         System.out.println("表达式解析时产生错误:"+e1.getMessage());                         e1.printStackTrace();                 }         } } // 第一个范例:表达式 65+403 计算结果为:468.0 // 第二个范例:表达式 65+403*4-125/25%4/3+4 计算结果为:1680.6666666666667 // 第三个范例:表达式解析时产生错误:括号的数量不匹配! // 第四个范例:表达式 (65+403)*4-125/(25%4)/3+4 计算结果为:1834.3333333333333 // 第五个范例:表达式解析时产生错误:除数不能为0! // 第六个范例:表达式 ((65+403)*4-125/(25%4))/3+4 计算结果为:586.3333333333334[/code]希望能帮到您。 另外我更希望,您提的这个问题不是由于一时兴起,不然我感觉我这三个多小时(将近4个小时)的时间,花的不值得啊。 呜呜~ 我得歇会去了。
相关文章
相关标签/搜索