表达式求值中后缀转换

这几天闲着无聊用安卓编个计算器，实现方法有很多种。

想想学过的算法课，干脆点击监听录入表达式，然后中缀转为后缀计算吧

顺便复习下栈的应用，也不算白学一门课。

由于学的是c语言的，然后上课没好好听，只好边发文章边学了。

书上讲的中后缀表达式转换可能对于人工来说相对麻烦点

忘了在哪看到的一篇帖子，快速的转换，下面列出来方法

a+b*c-(d+e)

第一步：按照运算符的优先级对所有的运算单位加括号~

式子变成：((a+(b*c))-(d+e))

第二步：转换前缀与后缀表达式

前缀：把运算符号移动到对应的括号前面则变成：-( +(a *(bc)) +(de))

把括号去掉：-+a*bc+de 前缀式子出现

后缀：把运算符号移动到对应的括号后面则变成：((a(bc)* )- (de)+ )-

把括号去掉：abc*-de+- 后缀式子出现

这个由于书上没有源程序，也没考虑实现上的简便性，回来在考虑。

接下来是书上的教程

根据学过的加减乘除容易知道计算符的优先级，然后对应的进出栈

代码写的不怎么样，都注释上了，希望对于想接触的有一定的帮助

上代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


private String a;//由于使用charAt,需要转换为String类型
    private String exp;//前缀表达式
    private String postExp;
    private Stack<String> stack;//存放操作符
    private Stack<Float> values;
    private StringBuffer sb;//将数字统计起来的    
    public Calculat(String exp) {
        this.exp = exp;
    }
    //将中缀表达式转换成后缀表达式
    public void transform() {
        sb = new StringBuffer();
        stack = new Stack<String>();
        for (int i = 0; i < exp.length(); ) {
            //注意，这个for循环没有i++ note1
            Log.i("main",exp+"  "+exp.length());
            Log.i("main",exp.charAt(i)+"");
            char ch = exp.charAt(i);
            //如果ch不是运算符号，则将其存入到postexp中
            if (Character.isDigit(ch) || ch == '.') {
                while (Character.isDigit(ch) || ch == '.') {
                    sb.append(ch);
                    ch = exp.charAt(++i);
                }
                sb.append('#');
            } else {
                switch (ch) {
                    case '(':
                        //左括号无论什么时候都要入栈，所以直接入栈就好了
                        stack.push("(");
                        break;
                    case ')':
                        //右括号要一直出栈直到遇到离他最近的左括号，然后把左括号出栈
                        while (stack.peek() != "(")
                            sb.append(stack.pop());
                        break;
                    case '+':
                    case '-':
                        //由于+-运算符优先级一样，干脆合并在一起，下面的*/也一样
                        while (stack.size() > 0 && stack.peek() != "(")
                            //由于+-优先级比较低，只要遇到了就出栈
                            sb.append(stack.pop());
                        a = Character.toString(ch);
                        stack.push(a);
                        break;
                    case '*':
                    case '/':
                        while (stack.size() > 0 && (stack.peek() == "*" || stack.peek() == "/") && stack.peek() != "(")
                            sb.append(stack.pop());
                        a = Character.toString(ch);
                        stack.push(a);
                        break;
                }
                ++i;
            }
        }
        while (stack.size() > 0)
            sb.append(stack.pop());

接下来是计算后缀表达式的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


    //计算后缀表达式
    public String evluate() {
        float a, b, c, d;
        postExp = sb.toString();
        values = new Stack<Float>();
        for (int i = 0; i < postExp.length(); ) {
            char ch = postExp.charAt(i);
            //计算后缀表达式相对比较简单了，就是碰到计算符提取两个数字，计算再入栈
            if (Character.isDigit(ch) || ch == '.') {
                d = 0;
                while (Character.isDigit(ch)) {
                    d = 10 * d + Integer.parseInt(ch + "");
                    ch = postExp.charAt(++i);
                }
                values.push(d);
            } else {
                switch (ch) {
                    case '+':
                        a = values.pop();
                        b = values.pop();
                        c = a + b;
                        values.push(c);
                        break;
                    case '-':
                        a = values.pop();
                        b = values.pop();
                        c = b - a;
                        values.push(c);
                        break;
                    case '*':
                        a = values.pop();
                        b = values.pop();
                        c = a * b;
                        values.push(c);
                        break;
                    case '/':
                        a = values.pop();
                        b = values.pop();
                        if (a != 0) {
                            c = b / a;
                            values.push(c);
                        } else {
                            System.out.println("the number is 0.cannot be /");
                            System.exit(0);
                        }
                        break;
                }
                i++;
            }
        }
        String tmp=String.valueOf(values.peek());
        return tmp;
    }

由于想练练手弄计算器，所以把这几个方法封装成了一个类，没有main函数

在百度的时候看到可以使用遍历的方法进行转换，生成二叉树，然后先序遍历生成前缀，后序遍历生成后缀，有时间考虑下吧。

还有通信网理论的论文没写呢

文章目录