使用中綴運算式實作一個簡易計算機

開學學演算法的第5天

使用中綴運算式基于堆疊實作一個簡易的中綴運算式，

實作思路：先對其判斷字符str.charAt(i)是數字還是運算子，如果是數字直接入數堆疊，如果是運算子先判斷是否堆疊空，堆疊空則直接入堆疊，堆疊不為空則判斷當前運算子優先級和堆疊頂運算子優先級比較，當前運算子優先小于等于堆疊頂運算子，出兩個數字堆疊，一個字符堆疊并做運算，將運算結果入堆疊，并將當前運算子入堆疊，依次遍歷完字符，最后判斷字符堆疊是否為空，為空直接出數字堆疊為最終結果，不為空則出數字堆疊兩個元素，出運算子堆疊一個元素并計算然后將結果入數字堆疊，直到運算子堆疊為空，

圖解：

class stack<E>{
    private E[] arr;
    private int size;

    public stack(int capacity){
        arr = (E[]) new Object[capacity];
    }

    //入堆疊
    public void push(E val){
        if (isFull()){
            ensureCapacity();
        }
        arr[size] = val;
        size = size+1;
    }

    //出堆疊
    public E pop(){
        //判空
        if (isEmpty()){
            throw new RuntimeException("空堆疊");
        }
        //出堆疊一次就要進行元素的移動
        E val = arr[this.size-1];
        this.size--;

        this.arr = Arrays.copyOf(this.arr,size);
        return val;
    }

    //判空
    public boolean isEmpty(){
        return this.size == 0;
    }

    //判滿
    public boolean isFull(){
        return this.size == this.arr.length;
    }

    //擴容
    public void ensureCapacity(){
        if (size == arr.length){
            this.arr = Arrays.copyOf(arr, arr.length *2 + 1);
        }
    }

    //獲取堆疊頂元素
    public E peek(){
        return this.arr[size-1];
    }
}

public class ComputerDemo {
    public static void main(String[] args) {
        stack<Integer> number = new stack<>(10);
        stack<Character> chars = new stack<>(10);
        String expression = "7*2*2-5+1-5+3-4";
        calculator(number,chars,expression);
    }
    //中綴
    public static void calculator(stack<Integer> number,stack<Character> chars,String expression){
        for (int i = 0; i < expression.length(); i++) {
            if (Character.isDigit(expression.charAt(i))){
                //表示當前字符為數字
                String s = String.valueOf(expression.charAt(i));
                int j = i+1;
                String tmp = new String();
                //這里出現70+2這種情況將數字拼接起來
                while (j < expression.length()){
                    if (Character.isDigit(expression.charAt(j))){
                        tmp+=expression.charAt(j);
                    }else {
                        break;
                    }
                    j++;
                }
                i = j -1;
                s += tmp;
                Integer value = new Integer(s);
                //將連續兩個數字的字符拼接起來并入堆疊
                number.push(value);
            }else{
                //運算子
                if (chars.isEmpty()){
                    //字符堆疊為空直接入堆疊
                    chars.push(expression.charAt(i));
                }else{
                    int priority = priority(expression.charAt(i));
                    Character peek = chars.peek();
                    int peeks = priority(peek);
                    //將當前字符與堆疊中的字符作比較
                    if (priority <= peeks){
                        int num1 = number.pop();
                        int num2 = number.pop();
                        Character pop = chars.pop();
                        int compute = compute(num1, num2, pop);
                        //將計算結果入堆疊
                        number.push(compute);
                        //將當前運算子入堆疊
                        chars.push(expression.charAt(i));
                    }else {
                        chars.push(expression.charAt(i));
                    }
                }
            }
        }
        //需要對其符號堆疊做出判空處理  如果為空則直接列印number堆疊即可，否則繼續計算
        while (!chars.isEmpty()){
            Character pop = chars.pop();
            Integer num1 = number.pop();
            Integer num2 = number.pop();
            int res = compute(num1, num2, pop);
            number.push(res);
        }

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

    //設定運算子的優先級，優先級越高數字值越大
    public static int priority(char oper){
        if (oper == '*' || oper == '/'){
            return 1;
        }else if (oper == '+' || oper == '-'){
            return 0;
        }else{
            return -1;
        }
    }


    //計算方法
    public static int compute(int num1,int num2,char oper){
        int res = 0;
        switch (oper){
            case '+':
                res = num1+num2;
                break;
            case '/':
                res = num2/num1;
                break;
            case '*':
                res = num1*num2;
                break;
            case '-':
                res = num2 - num1;
                break;
        }
        return res;
    }


}

點個贊唄~