栈实现四则运算--逆波兰运算（后缀表达式）

飞行日记之数据结构与算法分析——栈与四则运算

本次举例说明如何利用栈来完成简单的四则运算。

四则运算的前缀、中缀和后缀表达式（逆波兰运算）

• 前缀表达式计算方法：（3+4）x5-6 >>> - x + 3 4 5 6从右至左扫描，遇到数字则压入数栈，遇到运算符，弹出数栈顶两个数并作相应运算，计算结果入栈；重复上述过程直到前缀表达式最左端；
• 中缀表达式计算方法：正常表达式即中缀表达式。
• 后缀表达式计算方法：6 x(5 +(2 +3) x8) >>> 6 5 2 3 + 8 x + x从左到右扫描，遇到数字则压入数栈，遇到运算符，弹出数栈顶两个数并作相应运算，计算结果入栈；重复上述过程直到前缀表达式最右端；
• 代码实现：通过给定的后缀表达式，利用栈完成计算（包括多位数和小数点，不包括负数）；

package LeetCodeAQ;
import java.util.*;

public class PolandNotation {
    public static void main(String[] args) {
        //输入后缀表达式 每个数字和符号中间用 空格 隔开（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("结果="+resList);
        float res = calculate(resList);
        System.out.println("计算结果等于="+ 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;
    }
     
    //开始运算操作
    public static float calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        for(String item:list) {
            //用正则表达式匹配，此处可匹配正负数和小数
            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("运算符号不对劲啊");
                }
                stack.push(String.valueOf(res));    
            }
        }
        return Float.parseFloat(stack.pop());   
    }   
}

下一讲将具体给出怎么将中缀表达式转换成后缀表达式？以及其中的思路、难点和注意事项！

Quiet and Quick, Salute！