目录

栈实现计算器(中缀表达式)

处理思路

  1. 分别使用数栈numStack和符号栈operStack存放数和符号 https://gitee.com/lienhui68/picStore/raw/master/null/20200617175330.png

代码实现

  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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
package com.eh.ftd.dsa.ds.impl;

import com.eh.ftd.dsa.ds.Stack;
import com.google.common.collect.Lists;

import java.util.List;

/**
 * 计算器
 *
 * @author David Li
 * @create 2020/06/17 14:53
 */
public class Calculator {

    /**
     * 操作符集合
     */
    private static final List<Character> operators = Lists.newArrayList('+', '-', '*', '/');

    /**
     * 操作符类
     */
    class Operator implements Comparable<Operator> {
        private char operator;
        private int priority;

        public Operator(char operator) {
            switch (operator) {
                case '+':
                case '-':
                    this.operator = operator;
                    this.priority = 0;
                    break;
                case '*':
                case '/':
                    this.operator = operator;
                    this.priority = 1;
                    break;
            }
        }

        @Override
        public int compareTo(Operator o) {
            return this.priority - o.priority;
        }

        public char getOperator() {
            return operator;
        }
    }


    /**
     * 计算表达式
     *
     * @param expression
     * @return
     */
    public int calculate(String expression) {
        expression = expression.replace(" ", "");
        // 定义数栈和符号栈
        Stack<Integer> numStack = new ArrayStack<>(20);
        Stack<Operator> operStack = new ArrayStack<>(20);
        // 扫描表达式
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (isOperator(c)) {
                // 如果是操作符
                Operator curOper = new Operator(c);
                // 如果操作符栈是否为空则直接入操作符栈
                if (operStack.isEmpty()) {
                    operStack.push(curOper);
                    continue;
                }
                // 如果当前操作符优先级大于栈顶操作符也直接入栈
                Operator topOper = operStack.peek();
                if (curOper.compareTo(topOper) > 0) {
                    operStack.push(curOper);
                    continue;
                }
                /**
                 * num1=numStack.pop();
                 * num2=numStack.pop();
                 * oper = operStack.pop();
                 * num = num2 oper num1
                 * numStack.push(num);
                 * operStack.push(seg)
                 */
                int num1 = numStack.pop();
                int num2 = numStack.pop();
                Operator oper = operStack.pop();
                int res = calculate(num1, num2, oper);
                numStack.push(res);
                operStack.push(curOper);
            } else {
                StringBuilder sb = new StringBuilder(String.valueOf(c));
                // 如果是数字则判断是否为多位数
                if (i < expression.length() - 1) {
                    int j = i + 1;
                    if (j != expression.length()) {
                        char nextChar = expression.charAt(j);
                        if (!isOperator(nextChar)) {
                            sb.append(c);
                        }
                    } else {
                        sb.append(expression.charAt(i));
                    }
                }
                // 将数字入栈
                numStack.push(Integer.parseInt(sb.toString()));
            }
        }
        // 最后的加减法计算
        while (!operStack.isEmpty()) {
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            Operator oper = operStack.pop();
            int res = calculate(num1, num2, oper);
            numStack.push(res);
        }

        return numStack.peek();

    }

    /**
     * 判断是否是操作符
     *
     * @param c
     * @return
     */
    private boolean isOperator(char c) {
        if (operators.contains(c)) {
            return true;
        }
        return false;
    }


    /**
     * 对两个数进行计算
     *
     * @param num1
     * @param num2
     * @param operator
     * @return
     */
    private int calculate(int num1, int num2, Operator operator) {
        switch (operator.getOperator()) {
            case '+':
                return num1 + num2;
            case '-':
                return num2 - num1;
            case '*':
                return num1 * num2;
            case '/':
                if (num1 == 0) {
                    throw new RuntimeException("被除数不能为0");
                }
                return num2 / num1;
        }
        throw new RuntimeException("操作非法");
    }

    public static void main(String[] args) {
        Calculator calculator = new Calculator();
        System.out.println(calculator.calculate("2*3 + 8*7 + 3*4/6 -6"));
    }
}

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200617175718.png