4、逆波兰表达式求值——栈（java数据结构）

逆波兰表达式求值（栈）

逆波兰表示法是一种将运算符（operator）写在操作数（operand）后面的描述程序（算式）的方法。举个例子，我们平常用中缀表示法描述的算式（1 + 2）*（5 + 4），改为逆波兰表示法之后则是1 2 + 5 4 + *。相较于中缀表示法，逆波兰表示法的优势在于不需要括号。

请输出以逆波兰表示法输入的算式的计算结果。

输入格式:

在一行中输入1个算式。相邻的符号（操作数或运算符）用1个空格隔开。

输出格式:

在一行中输出计算结果。

限制:

2≤算式中操作数的总数≤100

1≤算式中运算符的总数≤99

运算符仅包括“+”、“-”、“*”，操作数、计算过程中的值以及最终的计算结果均在int范围内。

输入样例1:

4 3 + 2 -

输出样例1:

5

输入样例2:

1 2 + 3 4 - *

输出样例2:

-3

代码如下：

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s=input.nextLine();
        String[] a=s.split(" ");  //将输入的这行数据以空格分割，并存到数组a中
        Stack<Integer> intstack = new Stack<>();  //用于装数据中的整数
        for (int i=0;i<a.length;i++){
            if (judge(a[i])){   //判断是否为整数，如果是则加到栈中
                intstack.push(Integer.parseInt(a[i]));
            }else {   //如果不是整数，即遍历到运算符则开始运算
                int right=intstack.pop();
                int left=intstack.pop();
                switch (a[i]){
                    case "+": {
                        int sum = right+left;
                        intstack.push(sum);
                        break;
                    }
                    case "-": {
                        int sum = left-right;
                        intstack.push(sum);
                        break;
                    }
                    case "*": {
                        int sum = left*right;
                        intstack.push(sum);
                        break;
                    }
                    case "/": {
                        int sum = left/right;
                        intstack.push(sum);
                        break;
                    }
                }
            }
        }
        System.out.println(intstack.peek());    //输出栈顶元素，即最后的运算结果
    }

    static  boolean judge(String s){    //用于判断所输入的值是否为数字，数字则输出true，否则返回false
        try {
            int num=Integer.valueOf(s);
            return true;
        }catch (Exception e){
            return false;
        }
    }
}
           

其实逆波兰系数求值简单来讲就是每当遍历到运算符就将此运算符左边的两个数字弹出做四则运 算，然后把运算后的结果值放回栈中，最后弹出栈顶元素~