資料結構之使用棧實作電腦（加減乘除）

package com.ws.棧.棧電腦;

import java.util.Scanner;

public class Calculator {
    public static void main(String[] args) {
        String string;
        System.out.println("輸入一個算術式：");
        Scanner scanner=new Scanner(System.in);
        string=scanner.next();
        //建立兩個棧，一個數棧，一個符号棧
        ArrayStack shuStack=new ArrayStack(10);
        ArrayStack operStack=new ArrayStack(10);
        //定義相關變量
        int list=0;//用于掃描
        int shu1=0;//出棧數1
        int shu2=0;//出棧數2
        int oper=0;//操作符
        int jeiguo=0;//運算結果
        char ch=' ';//将每次掃描得到的char儲存到ch
        String pinjeshu = "";//用于多位數拼接
        //循環掃描算數式
        while (true){
            //依次得到算術式的每一個字元
            ch=string.substring(list,list+1).charAt(0);
            //判斷ch是什麼，然後進行相應處理
            if (operStack.ifOper(ch)){//是運算符
                //判斷目前的符号棧是否為空
                if (!operStack.ifFull()){//不為空處理
                    //如果符号棧不為空，就比較優先級，如果目前操作符優先級<=棧中操作符
                    if (operStack.printyouji(ch)<=operStack.printyouji(operStack.topkan())){
                        //從數棧出兩個數，從符号棧出一個符号進行計算
                        shu1=shuStack.pop();
                        shu2=shuStack.pop();
                        oper=operStack.pop();
                        jeiguo=shuStack.suan(shu1,shu2,oper);
                        //把運算結果入數棧
                        shuStack.add(jeiguo);
                        //把目前操作符入符号棧
                        operStack.add(ch);
                    }else {//目前操作符優先級>=棧中優先級
                        operStack.add(ch);
                    }
                }else {//為空就直接入符号棧
                    operStack.add(ch);
                }
            }
            else {//數字入數棧
//                shuStack.add(ch-48);//看編碼表可知，48  直接入數棧
                //1.處理多位數事不能直接入數棧，可能是多位數
                //2.處理數要看算術式字元串看下一位，數就繼續掃描，是符号就入棧
                      //如果是最後一位就直接入數棧
                //3.定義字元串變量用于拼接

                //處理多位數
                pinjeshu+=ch;
                if (list==string.length()-1){ //如果是最後一位就直接入數棧
                    shuStack.add(Integer.parseInt(pinjeshu));
                }else {
                    //判斷下一個字元是否是數字,是數字就繼續掃描，運算符就入棧,看後面一位，不是list後移
                    if (shuStack.ifOper(string.substring(list + 1, list + 2).charAt(0))) {
                        //後一位是運算符就入棧
                        shuStack.add(Integer.parseInt(pinjeshu));//pinjeshu是“1”或者“123”樣的字元串，需要轉換成一個字元
                        //清空拼接
                        pinjeshu = "";
                    }
                }
            }
            //讓字元+1，并判斷算術式是否掃描到最後,就結束
            list++;
            if (list>=string.length()){
                break;
            }
        }
        //當算數式掃描到最後就順序從數棧和符号棧中出棧，并計算
        while (true){
            //如果符号棧為空就得到最後結果,數棧中隻有一個數字就是結果
            if (operStack.ifFull()){
                break;
            }
            //否則就
            //從數棧出兩個數，從符号棧出一個符号進行計算
            shu1=shuStack.pop();
            shu2=shuStack.pop();
            oper=operStack.pop();
            jeiguo=shuStack.suan(shu1,shu2,oper);
            //把運算結果入數棧
            shuStack.add(jeiguo);
        }
        //将數棧出棧就是結果
        System.out.printf("表達式%s=%d\n",string,shuStack.pop());

    }
}

//建立棧
class ArrayStack{
    private int maxSize;//棧的大小
    private int[] stack;//數組，模拟棧
    private int top=-1;//棧頂，初始化-1

    //構造器
    public ArrayStack(int maxSize){
        this.maxSize=maxSize;
        stack=new int[this.maxSize];
    }

    //判斷棧滿
    public boolean ifMax(){
        return top==maxSize-1;//數組下标從0開始，-1
    }

    //判斷棧空
    public boolean ifFull(){
        return top==-1;
    }

    //入棧
    public void add(int value){
        //判斷棧滿
        if (ifMax()){
            System.out.println("棧滿");
            return;
        }
        //入棧
        top++;
        stack[top]=value;
    }

    //出棧
    public int pop(){
        //判斷棧是否為空
        if (ifFull()){
            //抛出異常
            throw new RuntimeException("棧空");
        }
        //出棧
        int value=stack[top];//先儲存棧頂
        top--;//棧頂下移
        return value;
    }

    //周遊棧
    //棧頂開始顯示資料
    public void list(){
        //判斷棧空
        if (ifFull()){
            System.out.println("棧空");
            return;
        }
        //棧頂開始顯示資料
        for (int i=top;i>=0;i--){
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

    //傳回運算符的優先級，由程式員來确定,數字越大，優先級越高
    public int printyouji(int oper){
        if (oper=='*'||oper=='/'){
            return 1;
        }else if (oper=='+'||oper=='-'){
            return 0;
        }else {
            return -1;//假定隻有+-*/
        }
    }
    //判斷是不是一個運算符
    public boolean ifOper(char val){
        return val=='+'||val=='-'||val=='*'||val=='/';
    }
    //計算方法
    public int suan(int shu1,int shu2,int oper){
        int jieguo=0;//用于存放結果
        switch (oper){
            case '+':
                jieguo=shu1+shu2;
                break;
            case '-':
                jieguo=shu2-shu1;//注意順序
                break;
            case '*':
                jieguo=shu1*shu2;
                break;
            case '/':
                jieguo=shu2/shu1;
            default:
                break;
        }
        return jieguo;
    }
    //傳回目前棧頂的值，不出棧
    public int topkan(){
        return stack[top];
    }
}