14.java 中綴表達式轉后綴表達式

思路如下：

1、初始化兩個棧，運算符棧和中間結果棧

2、從左至右掃描

3、遇到數時直接壓入s2

4、遇到運算符時，比較其與s1棧頂的優先級，有如下幾種情況：

1）s1為空或棧頂為“（”或此運算符優先級大于s1棧頂符優先級時，直接入棧

2）s1棧頂運算符優先級大于等于該運算符時，不斷從s1棧中彈出棧頂并壓入s2直到s1為空或優先級大于s1棧頂。然后將此運算符壓入s1

5、遇到括號時：

1）為左括號則直接壓入s2

2）為右擴號時則不斷彈出s1棧頂壓入s2直到遇到左括號時，停止彈出并將這一對括號丟棄

6、掃描到最右邊時結束循環

7、將s1中的運算符依次彈出并壓入s2

8、依次彈出s2中的元素并輸出，結果的逆序則為后綴表達式。

主要依賴兩個方法，

1、將中綴表達式分割轉換為一個list

需要考慮多位數，遍歷字符串s，不是數字則直接add入list，是數字則進入while循環直到結束或得到的后一位不為數字了結束拼接，add入list剛剛得到的拼接字符串

public static List<String> tolist(String s){
        List<String> list=new ArrayList<String>();
        String str="";
        char ch=' ';
        int i=0;
        do {
            if((s.charAt(i)<48)||(s.charAt(i)>57)){
                list.add(""+s.charAt(i));
                i++;
            }else {
                str="";
                while (i<s.length()&&s.charAt(i)>=48&&s.charAt(i)<=57){
                    str+=s.charAt(i);
                    i++;
                }
                list.add(str);
            }
        }while (i<s.length());
        return list;
    }

2、將分割后的list轉換為后綴表達式

定義兩個棧，但由于s2沒有pop的操作且之后還要倒序輸出所以這里以list來代替棧。遍歷list，依據上述描述來寫邏輯。

public static List<String> parseList(List<String> list){
        Stack<String> stack=new Stack<String>();
        List<String> ls=new ArrayList<String>();

        for (String item:list){
            if(item.matches("\\d+")){
                ls.add(item);
            }else if (item.equals("(")){
                stack.push(item);
            }else if (item.equals(")")){
                while (stack.size()!=0&&!stack.peek().equals("(")){
                    ls.add(stack.pop());
                }
                stack.pop();
            }else {
                while (stack.size()!=0&&oper.getvalue(stack.peek())>=oper.getvalue(item)){
                    ls.add(stack.pop());
                }
                stack.push(item);
            }

        }
        while (stack.size()!=0){
            ls.add(stack.pop());
        }
        return ls;
    }

posted @ 2022-03-29 00:00 水煮小白菜閱讀(146) 評論(0) 收藏舉報

刷新頁面返回頂部

codesslave

14.java 中綴表達式轉后綴表達式

公告