天不错啊

记录生活&学习

0%

中缀与后缀表达式计算.md

发表于 更新于 分类于

前言

数据结构与算法 -C语言实现
习题 3.19 3.20

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
package com.github.数据结构与算法分析.stack;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author JiHongYuan
 * @date 2021/6/14 13:45
 */
public class SuffixCalc {

    public static void main(String[] args) {
        String expression = "4.99 * 1.06 + 5.99 + 6.99 * 1.06";
        List<String> suffixList = infixTransformSuffix(expression);

        Stack<BigDecimal> stack = new Stack<>();
        for (String s : suffixList) {
            SymbolEnum symbol = SymbolEnum.getSymbolEnumByString(s);
            if (symbol == SymbolEnum.NONE) {
                stack.push(new BigDecimal(s));
            } else {
                BigDecimal i1 = stack.pop();
                BigDecimal i2 = stack.pop();
                BigDecimal iNew;
                switch (symbol) {
                    case ADD:
                        iNew = i1.add(i2);
                        break;
                    case SUB:
                        iNew = i1.subtract(i2);
                        break;
                    case MUL:
                        iNew = i1.multiply(i2);
                        break;
                    case DIV:
                        iNew = i1.divide(i2);
                        break;
                    default:
                        iNew = new BigDecimal("0.00");
                }
                stack.push(iNew);
            }
        }

        System.out.println(stack.pop());
    }

    /**
     * 中缀表达式转换成后缀表达式
     *
     * @param expression 中缀表达式
     * @return 后缀表达式
     */
    public static List<String> infixTransformSuffix(String expression) {
        List<String> suffixList = new ArrayList<>();

        Stack<SymbolEnum> stack = new Stack<>();
        for (String s : expression.split(SymbolEnum.NONE.symbol)) {
            SymbolEnum symbol = SymbolEnum.getSymbolEnumByString(s);
            if (symbol == SymbolEnum.NONE) {
                suffixList.add(s);
            } else {
                if (symbol == SymbolEnum.RIGHT_PARENTHESIS) {
                    suffixFiller(stack, suffixList, SymbolEnum.RIGHT_PARENTHESIS);
                } else if (stack.isEmpty() || stack.peek().priority > symbol.priority) {
                    stack.push(symbol);
                } else {
                    suffixFiller(stack, suffixList, SymbolEnum.NONE);
                    stack.push(symbol);
                }
            }
        }
        suffixFiller(stack, suffixList, SymbolEnum.NONE);
        return suffixList;
    }

    /**
     * 后缀表达式填充
     *
     * @param stack      数据源栈
     * @param suffixList 填充目标列表
     * @param symbol     当前表达式
     */
    public static void suffixFiller(Stack<SymbolEnum> stack, List<String> suffixList, SymbolEnum symbol) {
        while (!stack.isEmpty()) {
            SymbolEnum top = stack.peek();
            if (SymbolEnum.LEFT_PARENTHESIS == top) {
                if (symbol == SymbolEnum.RIGHT_PARENTHESIS) stack.pop();

                return;
            }
            suffixList.add(stack.pop().symbol);
        }
    }

    enum SymbolEnum {
        /**
         *
         */
        ADD("+", 4),
        SUB("-", 4),
        MUL("*", 3),
        DIV("/", 3),
        LEFT_PARENTHESIS("(", 1),
        RIGHT_PARENTHESIS(")", 1),
        NONE(" ", -1);
        String symbol;
        int priority;

        SymbolEnum(String symbol, int priority) {
            this.symbol = symbol;
            this.priority = priority;
        }

        public static SymbolEnum getSymbolEnumByString(String s) {
            for (SymbolEnum value : SymbolEnum.values()) {
                if (s.equals(value.symbol)) {
                    return value;
                }
            }
            return NONE;
        }
    }

}