飛行日記之?dāng)?shù)據(jù)結(jié)構(gòu)與算法分析——棧與四則運(yùn)算

本次舉例說明如何利用棧來完成簡單的四則運(yùn)算仁讨。

四則運(yùn)算的前綴乖阵、中綴和后綴表達(dá)式（逆波蘭運(yùn)算）

• 前綴表達(dá)式計(jì)算方法：（3+4）x5-6 >>> - x + 3 4 5 6從右至左掃描扔枫，遇到數(shù)字則壓入數(shù)棧，遇到運(yùn)算符祝迂，彈出數(shù)棧頂兩個(gè)數(shù)并作相應(yīng)運(yùn)算姐军，計(jì)算結(jié)果入棧；重復(fù)上述過程直到前綴表達(dá)式最左端宇攻；
• 中綴表達(dá)式計(jì)算方法：正常表達(dá)式即中綴表達(dá)式惫叛。
• 后綴表達(dá)式計(jì)算方法：6 x(5 +(2 +3) x8) >>> 6 5 2 3 + 8 x + x從左到右掃描，遇到數(shù)字則壓入數(shù)棧逞刷，遇到運(yùn)算符嘉涌，彈出數(shù)棧頂兩個(gè)數(shù)并作相應(yīng)運(yùn)算，計(jì)算結(jié)果入棧夸浅；重復(fù)上述過程直到前綴表達(dá)式最右端仑最；
• 代碼實(shí)現(xiàn)：通過給定的后綴表達(dá)式，利用棧完成計(jì)算（包括多位數(shù)和小數(shù)點(diǎn)帆喇，不包括負(fù)數(shù)）警医；

package LeetCodeAQ;
import java.util.*;

public class PolandNotation {
    public static void main(String[] args) {
        //輸入后綴表達(dá)式 每個(gè)數(shù)字和符號(hào)中間用 空格 隔開（1-2*3）+（（5*3-1）*2-1）
        String suffixExpression = "1 2 3 * - 5 3 * 1 - 2 * 1 - +";
        // 將字符串存入到列表中
        List<String> resList = getList(suffixExpression);
        System.out.println("結(jié)果="+resList);
        float res = calculate(resList);
        System.out.println("計(jì)算結(jié)果等于="+ res);
    }
    
    
    //將字符串存放到列表中
    public static List<String> getList(String suffixExpression){
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for(String s:split){
            list.add(s);
        }
        return list;
    }
     
    //開始運(yùn)算操作
    public static float calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        for(String item:list) {
            //用正則表達(dá)式匹配，此處可匹配正負(fù)數(shù)和小數(shù)
            if(item.matches("^[+-]?\\d+(\\.\\d+)?$")) {
                stack.push(item);
            }else {
                float num1 = Float.parseFloat(stack.pop());
                float num2 = Float.parseFloat(stack.pop());
                float res = 0;
                if(item.equals("+")) {
                    res = num1 + num2;
                }else if(item.equals("-")) {
                    res = num2 - num1;
                }else if(item.equals("*")) {
                    res = num1 * num2;
                }else if(item.equals("/")){
                    res = num2 / num1;
                }else {
                    throw new RuntimeException("運(yùn)算符號(hào)不對(duì)勁啊");
                }
                stack.push(String.valueOf(res));    
            }
        }
        return Float.parseFloat(stack.pop());   
    }   
}

下一講將具體給出怎么將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式坯钦？以及其中的思路预皇、難點(diǎn)和注意事項(xiàng)侈玄！

Quiet and Quick, Salute！