java - 评估前缀表达式

Question

问题是这样的:

“当运算符写在操作数之前时，表达式采用前缀形式。以下是前缀表达式及其计算结果的一些示例:

        Expression____________________Value_
        12                            12
        + 2   51                      53
        * 5   7                       35
        *  + 16  4        + 3 1       80

以整数开头的表达式(例如 12)是计算结果为自身的前缀表达式。否则，如果表达式以运算符开头且后跟两个前缀表达式，则该表达式是前缀表达式。在后一种情况下，表达式的值是根据其组成前缀子表达式的值递归计算的。

编写一个程序，允许用户在文本字段中输入前缀表达式。程序读取表达式，对其求值，然后在合适的 GUI 组件中显示该值。假设用户输入仅使用正整数以及两个运算符 + 和 * 的表达式。您的程序应该使用一个堆栈来存储计算时的子表达式的值，并使用另一个堆栈来存储尚未应用的运算符。”

无论如何，我看不到使用运算符堆栈和表达式堆栈来解决它。然而，用一个堆栈并从相反的方向进行求解是非常简单的。

Answer 1

一种解决方案是从字符串末尾开始并将操作数放入堆栈中。每当遇到运算符时，弹出最后两个整数，应用运算符并再次压入堆栈。

import java.util.ArrayDeque;
import java.util.Deque;

public class PrefixEvaluator {

    public static void main(String[] args) {
        String[] prefixStr = "* + 16 4        + 3 1 ".split(" ");
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i=prefixStr.length-1;i>-1;i--){
            String s = prefixStr[i];
            if(s.equals("")){
                continue;
            }
            if(s.equals("+")){
                stack.push(stack.poll()+stack.poll());
            }else if(s.equals("*")){
                stack.push(stack.poll() * stack.poll());
            }else{
                stack.push(Integer.parseInt(s));
            }
        }
        System.out.println(stack.poll());
    }

}