[数据结构与算法]数据结构——栈（计算器实现原理）

实现一个最简单的计算器，规定：

• 只有+、-、*、/，没有小括号
• 数字只能是0-9之间的数字，不能有两位数。

Main函数及计算函数代码：

package algorithm.stack;

public class Calculator {
    public static void main(String[] args) {
        String s = "3+6*8/7";
        System.out.println(cal(s));
    }

    public static float cal(String s) {
        int index = 0;
        float num1 = 0;
        float num2 = 0;
        char oper = ' ';
        MyStack numStack = new MyStack(10);
        MyStack operStack = new MyStack(10);
        float result;
        while (index <= s.length() - 1) {
            //如果是字符
            if (MyStack.chType(s.charAt(index)) == 0) {
                //如果是栈空
                if (operStack.isEmpty() || MyStack.priority(s.charAt(index)) > MyStack.priority((char) operStack.peek())) {
                    operStack.push(s.charAt(index));
                }
                //看新的符号优先级小于等于上一个符号
                else if (MyStack.priority(s.charAt(index)) <= MyStack.priority((char) operStack.peek())) {
                    oper = (char) operStack.pop();
                    num1 = numStack.pop();
                    num2 = numStack.pop();
                    result = MyStack.calcu(num1, num2, oper);
                    numStack.push(result);
                    operStack.push(s.charAt(index));
                }

            }
            //如果是数字
            if (MyStack.chType(s.charAt(index)) == 1) {
                numStack.push(s.charAt(index) - 48);
            }
            index++;
        }
        char ch = ' ';
        float n1 = 0;
        float n2 = 0;
        float val;
        //将算式入栈完毕后，计算剩下的数
        while (!operStack.isEmpty()) {
            ch = (char) operStack.pop();
            n1 = numStack.pop();
            n2 = numStack.pop();
            val = MyStack.calcu(n1, n2, ch);
            numStack.push(val);
        }
        return numStack.peek();
    }
}

栈及相关功能：

package algorithm.stack;

public class MyStack {
    //栈的大小
    private final int maxSize;
    //实现栈的数组
    private final float[] stackArray;
    //栈顶
    private int top = -1;

    //构造器
    public MyStack(int maxSize) {
        this.maxSize = maxSize;
        stackArray = new float[maxSize];
    }

    //栈满
    public boolean isFull() {
        return top == maxSize - 1;
    }

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

    //入栈
    public void push(float val) {
        if (isFull()) {
            System.out.println("栈满，操作失败！");
            return;
        }
        stackArray[++top] = val;
    }

    //出栈
    public float pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空，出栈失败");
        }
        float val = stackArray[top];
        top--;
        return val;
    }

    //查看栈顶元素
    public float peek() {
        return stackArray[top];
    }

    //遍历栈
    public void show() {
        if (isEmpty()) {
            System.out.println("栈空，打印失败！");
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("%d\t", stackArray[i]);
            System.out.println();
        }
    }

    //定义符号的优先级
    //+-为0
    //*/为1
    public static int priority(char oper) {
        if (oper == '+' || oper == '-') {
            return 0;
        } else{
            return 1;
        }
    }
    //判断输入的字符是否合法

    /**
     *
     * @param ch
     * @return 0表示是字符，1表示是数字
     */
    public static int chType(char ch){
        String s = "0123456789";
        //是否为字符
        if (ch == '+'||ch == '-'||ch=='*'||ch=='/'){
            return 0;
        }
        //是否为数字
        String temp = String.valueOf(ch);
        if (s.contains(temp)){
            return 1;
        }
        //如果都不是
        throw new RuntimeException("非法字符");
    }

    //计算过程
    public static float calcu(float num1, float num2, char op) {
        float val=0;
        switch (op){
            case '+':
                val = num1+num2;
                break;
            case '-':
                val = num2-num1;
                break;
            case '*':
                val = num1*num2;
                break;
            case '/':
                val = num2/num1;
                break;
            default:break;
        }
        return val;
    }

}

运算结果：

float保存:

计算器结果：