栈实现计算器

计算器

/**
 * @author 缪广亮
 * @version 1.0
 */
@SuppressWarnings({"all"})
public class Calculator {
    public static void main(String[] args) {
//        完成表达式的运算
        String expression = "770+2*6-4+1";
//        创建数栈和字符栈
        LinkedListStack2 numStack = new LinkedListStack2();
        LinkedListStack2 operationStack = new LinkedListStack2();

        int index = 0;//用于扫描
        int num1 = 0;
        int num2 = 0;
        int operation = ' ';
        int res = 0;
        String keepNum = "";//用于拼接多位数
        char ch = ' ';//用于将每次扫描得到的char保存到ch
//        while循环的扫描expression
        while (true) {
//            依次得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
//            判断ch是什么，然后判断
            if (operationStack.isOper(ch)) {//如果是运算符
//                判断当前的符号栈是否为空
                if (!operationStack.isEmpty()) {
//                    如果符号栈有操作符，进行比较，
//                    如果当前的操作符的优先级小于或者等于栈中栈顶的操作符
//                    首先从数栈pop除两个数，再从符号栈pop出一个符号，运算得出结果
//                    最后将当前的操作符入符号栈
                    if (operationStack.priority(ch) <= operationStack.priority((char) operationStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        operation = operationStack.pop();
                        res = numStack.cal(num1, num2, operation);
//                        把运算结果入数栈
                        numStack.push(res);
//                        将当前的操作符入符号栈
                        operationStack.push(ch);
                    } else {
//                        如果当前的操作符的优先级大于栈中的操作符，直接入符号栈
                        operationStack.push(ch);
                    }
                } else {
//                    如果栈为空直接入栈
                    operationStack.push(ch);
                }
            } else {
//                如果是数，直接入数栈
//                numStack.push(ch-48);//得到的是字符'1'，而数字1是与字符'1'相差48
//                 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
//                 在处理数，需要向expression的表达式的index后再看一位，
//                 如果是数就继续进行扫描，如果是符号才入栈
//                定义一个变量字符串，用于拼接
//                处理多位数
                keepNum += ch;
//                如果ch已经是expression的最后一位，直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
//                判断下一个字符是不是字符，如果是数字，就继续扫描，如果是运算符则入栈
//                注意看后一位，不是index++
                    if (operationStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
//                    如果后一位是运算符。则入栈keepNum="1"/"123"
                        numStack.push(Integer.parseInt(keepNum));
//                    清空keepNum
                        keepNum = "";

                    }
                }
            }
//            index+1,并判断是否扫描到expression最后
            index++;
            if (index >= expression.length())
                break;
        }
//        当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运算
        while (true) {
//            如果符号栈为空，则计算到最后的结果，数栈中只有一个数字即结果
            if (operationStack.isEmpty())
                break;
            num1 = numStack.pop();
            num2 = numStack.pop();
            operation = operationStack.pop();
            res = numStack.cal(num1, num2, operation);
//                        把运算结果入数栈
            numStack.push(res);
        }
//        将数栈的
        System.out.printf("表达式%s = %d", expression, numStack.pop());
    }
}

@SuppressWarnings({"all"})
//链表栈
class LinkedListStack2 {
    private Node top;

    private class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    //  入栈
    public void push(int data) {
        Node newNode = new Node(data);
        if (top == null) {
            top = newNode;
        } else {
            newNode.next = top;
            top = newNode;
        }
    }

    //    出栈
    public int pop() {
        if (top == null) {
            throw new RuntimeException("栈空");
        }
        int data = top.data;
        top = top.next;
        return data;
    }

    //    栈顶元素
    public int peek() {
        if (top == null)
            throw new RuntimeException("栈空");
        return top.data;
    }

    //    栈空
    public boolean isEmpty() {
        return top == null;
    }

    //    遍历
    public void printStack() {
//        top指针不能动，需要一个current的辅助指针
        Node current = top;
        if (top == null)
            throw new RuntimeException("栈空");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    //判断运算符的优先级，用数字代表优先级，数字越大，优先级越高
    public int priority(char oper) {
        if (oper == '*' || oper == '/')
            return 1;
        else if (oper == '+' || oper == '-')
            return 0;
        else
            return -1;//目前的运算符只含有+-*/
    }

    //    判断是不是运算符
    public boolean isOper(char oper) {
        return oper == '*' || oper == '/' || oper == '+' || oper == '-';
    }

    //    计算方法
    public int cal(int num1, int num2, int oper) {
        int res = 0;//计算结果
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;//后pop的数作为被减数，先pop作为减数
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;//后pop的数作为被除数，先pop作为除数
                break;
        }
        return res;
    }
}