黑马程序员技术交流社区

标题: 给定任意的一个含数学运算符的字符串，怎么求这个字符串转换成数学表达式的值 [打印本页]

---

作者: 毕仁杰    时间: 2011-7-30 16:53
标题: 给定任意的一个含数学运算符的字符串，怎么求这个字符串转换成数学表达式的值
下午写一个计算器模拟程序，得到了计算的算术表达式，怎么求出它的值。

例如有如下的数学表达式：（表达式是取的计算器输入要计算的算术式）
8+4-5/4+6.0-2*3   结果为 10.75
String value = "8+4-5/4+6.0-2*3";
怎么从这个字符串中算出表达式的值？

而且还需要注意的是：
字符串value  的值  是变化的    随着计算器所要求的表达式改变
如：下次我要计算  8 * 2 - 7
那么通过一个函数  我们得到了   value = "8 * 2 - 7"
那么表达式的值也就变化了。

也就是说：给定任意的一个含数学运算符的字符串，怎么求这个字符串转换成数学表达式的值。
注意：
5/4要解释成1.25（小数点的位数可以不考虑）
关于运算符的优先级还是得考虑的。
[ 本帖最后由 毕仁杰 于 2011-07-31  11:22 编辑 ]

---

作者: 匿名    时间: 2011-7-31 10:09
标题: 回复 楼主 的帖子
楼主同学，算术表达式的结果最后能是字符串类型么？
程序应该为：
//5/4默认会先按整数进行运算，会四舍五入，所以因提前转为double类型的数据；
double a = 8+4-(double)5/4+6.0-2*3;  
System.out.println(a);//结果为 10.75

---

作者: 匿名    时间: 2011-7-31 11:16
标题: 回复 沙发 的帖子
先感谢你顶贴 ！
我的意思是：
String value = "8+4-5/4+6.0-2*3";   只是举的一个例子
实际上  计算器每次计算的值是不一样的
如下次计算 8 -6+7
那么value = “8 - 6 + 7"
也就是说 表达式是变化的  （随着计算器输入的值变化）
那么将字符串转换为数学表达式后  值也随之改变。

---

作者: 匿名    时间: 2011-7-31 15:12
还好我宝刀未老，嘿嘿，您要的这个程序，连写带测试，用了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个小时)的时间，花的不值得啊。
呜呜~ 我得歇会去了。

---

作者: 匿名    时间: 2011-7-31 15:32
标题: 回复 楼主 的帖子
哇，没发现这个问题里面有好多东西，受教受教，顶一下帖子，虎哥做的很细致，我要保存好这个帖子，仔细研究下

---

作者: 常帅    时间: 2011-7-31 15:40
标题: 回复 板凳 的帖子
果然是大神级任务....牛人
让我感觉有种编译原理里边曾学过的一些东西,....   
但是都已经模糊了
[ 本帖最后由 常帅 于 2011-07-31  16:18 编辑 ]

---

作者: 匿名    时间: 2011-7-31 17:12
标题: 回复 板凳 的帖子
代码看完了！ 再顶一下

---

作者: 毕仁杰    时间: 2011-7-31 19:04
标题: 回复 板凳 的帖子
计算器界面程序（启动运行类）如下：

1. package GUI.calculator;
   
2. 
   
3. import java.awt.BorderLayout;
   
4. import java.awt.GridLayout;
   
5. import java.awt.event.ActionEvent;
   
6. import java.awt.event.ActionListener;
   
7. import java.awt.event.WindowAdapter;
   
8. import java.awt.event.WindowEvent;
   
9. 
   
10. import javax.swing.JButton;
    
11. import javax.swing.JFrame;
    
12. import javax.swing.JOptionPane;
    
13. import javax.swing.JPanel;
    
14. import javax.swing.JTextField;
    
15. import javax.swing.WindowConstants;
    
16. 
    
17. public class Calculator extends JFrame {
    
18. 
    
19.         /**
    
20.          * 综合运用Swing的知识，做一个模拟的计算器
    
21.          *
    
22.          */
    
23. 
    
24.         // 定义一个显示计算器数据的显示文本框,由于外部需要设置文本框的值，故设置为成员变量
    
25.         private JTextField jtf = new JTextField();
    
26. 
    
27.         public void init() {
    
28.                 // 设置主窗口的大小
    
29.                 setSize(300, 300);
    
30. 
    
31.                 // 设置计算器的标题
    
32.                 setTitle("Calculator");
    
33. 
    
34.                 // 当点击关闭按钮时，设置成什么也不做。
    
35.                 this.setDefaultCloseOperation(WindowConstants.DO_NOTHING_ON_CLOSE);
    
36. 
    
37.                 // 显示一个消息提示对话框
    
38.                 JOptionPane.showMessageDialog(this, "程序正在启动, 请稍等……");
    
39. 
    
40.                 // 获得JFrame中内置的JRootPane对象。
    
41.                 JPanel jr = (JPanel) this.getContentPane();
    
42. 
    
43.                 // 设置主程序窗口的布局管理器
    
44.                 jr.setLayout(new BorderLayout());
    
45. 
    
46.                 // 设置文本框的对齐方式为右对齐
    
47.                 jtf.setHorizontalAlignment(JTextField.RIGHT);
    
48. 
    
49.                 JPanel jp = new JPanel();
    
50. 
    
51.                 // 设置计算器面板的布局管理器 4行4列
    
52.                 jp.setLayout(new GridLayout(4, 4));
    
53. 
    
54.                 // 创建16个按钮，即计算器界面的按键 可以只创建一个JButton 实例化16个对象。
    
55.                 JButton jb11 = new JButton("1");
    
56.                 JButton jb12 = new JButton("2");
    
57.                 JButton jb13 = new JButton("3");
    
58.                 JButton jb14 = new JButton("+");
    
59.                 JButton jb21 = new JButton("4");
    
60.                 JButton jb22 = new JButton("5");
    
61.                 JButton jb23 = new JButton("6");
    
62.                 JButton jb24 = new JButton("-");
    
63.                 JButton jb31 = new JButton("7");
    
64.                 JButton jb32 = new JButton("8");
    
65.                 JButton jb33 = new JButton("9");
    
66.                 JButton jb34 = new JButton("*");
    
67.                 JButton jb41 = new JButton("0");
    
68.                 JButton jb42 = new JButton("AC");
    
69.                 JButton jb43 = new JButton("=");
    
70.                 JButton jb44 = new JButton("/");
    
71. 
    
72.                 // 将16个按键添加到面板JPanel上
    
73.                 jp.add(jb11);
    
74.                 jp.add(jb12);
    
75.                 jp.add(jb13);
    
76.                 jp.add(jb14);
    
77.                 jp.add(jb21);
    
78.                 jp.add(jb22);
    
79.                 jp.add(jb23);
    
80.                 jp.add(jb24);
    
81.                 jp.add(jb31);
    
82.                 jp.add(jb32);
    
83.                 jp.add(jb33);
    
84.                 jp.add(jb34);
    
85.                 jp.add(jb41);
    
86.                 jp.add(jb42);
    
87.                 jp.add(jb43);
    
88.                 jp.add(jb44);
    
89. 
    
90.                 // 将显示数据的文本框和计算器按键组添加到主窗口上
    
91.                 jr.add(jtf, BorderLayout.NORTH);
    
92. 
    
93.                 // 省略的位置为Center
    
94.                 jr.add(jp);
    
95. 
    
96.                 // 给计算器界面按钮注册事件监听器
    
97.                 MyActionListener mal = new MyActionListener();
    
98.                 jb11.addActionListener(mal);
    
99.                 jb12.addActionListener(mal);
    
100.                 jb13.addActionListener(mal);
     
101.                 jb14.addActionListener(mal);
     
102.                 jb21.addActionListener(mal);
     
103.                 jb22.addActionListener(mal);
     
104.                 jb23.addActionListener(mal);
     
105.                 jb24.addActionListener(mal);
     
106.                 jb31.addActionListener(mal);
     
107.                 jb32.addActionListener(mal);
     
108.                 jb33.addActionListener(mal);
     
109.                 jb34.addActionListener(mal);
     
110.                 jb41.addActionListener(mal);
     
111.                 jb42.addActionListener(mal);
     
112.                 jb43.addActionListener(mal);
     
113.                 jb44.addActionListener(mal);
     
114. 
     
115.                 this.setVisible(true);
     
116. 
     
117.                 // 由于我们设置了单击关闭按钮时什么也不做，所以我们需要设置关闭按钮的事件监听器
     
118.                 this.addWindowListener(new WindowAdapter() {
     
119.                         @Override
     
120.                         public void windowClosing(WindowEvent e) {
     
121.                                 // 设置一个选择对话框。
     
122.                                 int choice = JOptionPane.showConfirmDialog(Calculator.this,
     
123.                                                 "你确定退出吗？", "程序结束", JOptionPane.OK_CANCEL_OPTION,
     
124.                                                 JOptionPane.QUESTION_MESSAGE);
     
125.                                 // 判断对话框的按钮按下的值
     
126.                                 if (choice == JOptionPane.OK_OPTION) {
     
127.                                         dispose();
     
128.                                         System.exit(0);
     
129.                                 }// 如果单击的是取消，那我们什么也不做
     
130.                         }
     
131.                 });
     
132.         }
     
133. 
     
134.         public static void main(String[] args) {
     
135.                 new Calculator().init();
     
136.         }
     
137. 
     
138.         /*
     
139.          * 事件监听器定义为一个内部类： 刚开始时我的想法是重新建立一个源文件：MyActionListener.java
     
140.          * 这个源文件是实现了ActionListener接口，但是当我继续往下写的时候，我发现了一个十分严重的问题：
     
141.          * 在事件处理的方法中要创建一个Calculator类，获得它的方法，我们不能再创建一个计算器界面程序
     
142.          * 也就是说计算器主界面至始至终只有一个，即Calculator类只创建一个实例化对象。
     
143.          */
     
144.         // 看视频前我定义的是一个内部类，看完以后实际上可以直接在Calculator类上实现ActionListener接口，唉！没想到啊！
     
145.         public class MyActionListener implements ActionListener {
     
146. 
     
147.                 @Override
     
148.                 public void actionPerformed(ActionEvent e) {
     
149.                         if (e.getActionCommand().equals("=")) {
     
150.                                 String str = jtf.getText().trim();
     
151.                                 ExpressionParser ep = new ExpressionParser(str);
     
152.                                 try {
     
153.                                         double value = ep.parse();
     
154.                                         System.out.print("表达式 " + str + " 计算结果为：" + value);
     
155.                                         jtf.setText(new Double(value).toString());
     
156.                                 } catch (Exception e1) {
     
157.                                         System.out.println("表达式解析时产生错误:" + e1.getMessage());
     
158.                                         e1.printStackTrace();
     
159.                                 }
     
160.                         } else if (e.getActionCommand().equals("AC")) {
     
161.                                 jtf.setText("");
     
162.                         } else {
     
163.                                 jtf.setText(jtf.getText() + e.getActionCommand());
     
164.                         }
     
165.                 }
     
166. 
     
167.         }
     
168. 
     
169. }

复制代码

想要运行这个简易计算器，还得有#4虎哥的实现计算功能那2个类，综合起来，就行了！
[ 本帖最后由 毕仁杰 于 2011-07-31  19:23 编辑 ]

---

作者: 匿名    时间: 2011-7-31 20:02
嗯，测试完毕，合格！哈哈。

---

作者: 匿名    时间: 2011-7-31 23:05
不错，虎子是高手！

---

作者: 匿名    时间: 2011-8-8 08:18
学习了。。。

---

作者: yanping158    时间: 2013-12-5 17:15

匿名者 发表于 2011-7-31 15:12
还好我宝刀未老，嘿嘿，您要的这个程序，连写带测试，用了3个多小时(别说我菜，毕竟我是专门为了你工作3个 ...

神级大佬，转走了:lol

---

作者: ╭⌒风轻云淡    时间: 2014-5-27 14:47
虎哥的实现计算功能那2个类

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2