鹹魚學資料結構和算法——中綴表達式轉字首表達式計算機求值

目錄

一、中綴表達式轉字首表達式計算機求值算法介紹

二、中綴表達式轉字首表達式計算機求值代碼實作

一、中綴表達式轉字首表達式計算機求值算法介紹

1.将中綴表達式轉成字首表達式，具體算法和代碼實作可參考我的部落格鹹魚學資料結構與算法——中綴表達式轉字首表達式

2.字首表達式計算機求值，具體算法和代碼實作可參考我的部落格鹹魚學資料結構和算法——字首表達式計算機求值

二、中綴表達式轉字首表達式計算機求值代碼實作

public class PolandNotationCalculator {

    public static void main(String[] args) {
        String InfixExperssion="(3+4)*5-6";
        Stack<String> numStack =new Stack<String>();
        System.out.println("中綴表達式為:"+InfixExperssion);
        List<String> PrefixExperssion=InfixToPrefix(InfixExperssion);
        System.out.println("字首表達式為:"+PrefixExperssion);
        PrefixCalculate(PrefixExperssion,numStack);
        System.out.println("最後的結果為:"+numStack.pop());

    }

//    中綴表達式轉字首表達式
 


    public static List<String> InfixToPrefix(String infixExperssion){
//        從右向左掃描
        int index=infixExperssion.length()-1;
//      用來存放字首表達式
        List<String> resultList=new ArrayList<String>();
//      用來存放運算符
        Stack<String> operStack=new Stack<String>();
//      用來拼接數字，多位數字
        String joint="";
        while (true){
//          當掃描完畢後，退出循環
            if(index<0){
                break;
            }
//            如果掃描到是操作數，直接将結果加入到結果list中
//            如果是多位數的問題已經解決
            if (isNum(infixExperssion.charAt(index))){
//                由于是從右向左掃描，是以拼接要從右側開始拼接
                joint=infixExperssion.charAt(index)+joint;
//              判斷是否越界，如果越界則不需要比較
                if(index>1){
//                    判斷下一個字元是否為數字
                    if(!isNum(infixExperssion.charAt(index-1))){
                        resultList.add(joint);
                        joint="";
//                      執行完成後讓index加一，不然會陷入死循環
                        index--;

                    }else {
                        index--;
                    }
//              已經是最後一位數了，不需要看下一位了
                }else {
                    resultList.add(joint);
                    joint="";
                    index--;
                }
//          如果是運算符，根據運算符優先級判斷運算符是否進入運算符棧
            }else if(isOper(infixExperssion.charAt(index))){
                char oper=infixExperssion.charAt(index);
//              如果為空，則直接加入到運算符中
                if (operStack.empty()){
                    operStack.push(String.valueOf(oper));
                    index--;
//              如果優先級大于運算符棧頂運算符的優先級，将運算符加入到運算符棧中
                }else if(Priority(oper)>Priority(operStack.peek().charAt(0))){
                    operStack.push(String.valueOf(oper));
                    index--;
//              将運算符棧棧頂的運算符加入到List數組中
                }else {
                    resultList.add(operStack.pop());
//                    index++;
                }

//          如果是右括号，将右括号放入運算符棧中
            }else if(infixExperssion.charAt(index)==')'){
                operStack.push(String.valueOf(infixExperssion.charAt(index)));
                index--;
//          根據右括号來去除左括号
            } else if(infixExperssion.charAt(index)=='('){

                while (!operStack.empty()&&!operStack.peek().equals(")")){
                    resultList.add(operStack.pop());
                }
//             丢棄右括号
                operStack.pop();
                index--;
            }
        }
//      将運算符棧中的運算符彈到list中
        while (!operStack.empty()){
            resultList.add(operStack.pop());
        }
//      将結果反轉
        Collections.reverse(resultList);
        return resultList;
    }




    public static int Priority(char ch){
        if (ch=='+'||ch=='-'){
            return 1;
        }else if (ch=='*'||ch=='/'){
            return 2;
        }else {
            return 0;
        }
    }

    public static void PrefixCalculate(List<String> PrefixExperssion, Stack<String> numStack){
        //        從右向左掃描
        for (int i=PrefixExperssion.size()-1;i>=0;i--){
           System.out.println(PrefixExperssion.get(i));
            if (isNum(PrefixExperssion.get(i))){
//                System.out.println("測試入棧資料"+PrefixExperssionSplit[i]);
                numStack.push(PrefixExperssion.get(i));
            }else {
//              棧頂數字
                int num1=Integer.valueOf(numStack.pop());
//              次棧頂數字
                int num2=Integer.valueOf(numStack.pop());
                String opr=PrefixExperssion.get(i);
                int res=Calculate(num2,num1,opr);
                numStack.push(String.valueOf(res));
            }

        }


    }


  
    public static boolean isOper(char oper){
        if(oper=='+'||oper=='-'||oper=='*'||oper=='/'){
            return true;
        }else {
            return false;
        }
    }
    public static boolean isNum(char num){
        if(num>=48&&num<=57){
            return true;
        }else {
            return false;
        }
    }

    public static boolean isNum(String str){
        if(str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){
            return false;
        }else {
            return true;
        }
    }

    public static int Calculate(int num1,int num2,String opr){
        int res=0;
        switch (opr){
            case "+":
                res=num1+num2;
                break;
            case "-":
                res=num2-num1;
                break;
            case "*":
                res=num1*num2;
                break;
            case "/":
                res=num2/num1;
                break;
            default:
                break;
        }
        return res;
    }

}