题解 | #逆波兰表达式求值#

import java.util.*;


public class Solution {
    
    static int operator(int n1, int n2, String op) {
        if (op.equals("+")) return n1 + n2;
        else if (op.equals("-")) return n1 - n2;
        else if (op.equals("*")) return n1 * n2;
        else if (op.equals("/")) return n1 / n2;
        else return -1;
    }
    
    static boolean isOperator(String op) {
        return op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/");
    }
    
    static int solve01(String[] tokens) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        for (int i = 0 ; i < tokens.length; ++i) {
            if (isOperator(tokens[i])) {
                Integer num1 = stack.pop();
                Integer num2 = stack.pop();
                Integer res = operator(num2, num1, tokens[i]);
                stack.push(res);
            }
            else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.pop();
    }
    
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串一维数组 
     * @return int整型
     */
    public int evalRPN (String[] tokens) {
        // write code here
        return solve01(tokens);
    }
}


/////////////////////链表
/**
 * 栈的实现 -- 链表
 * 优点: 使用灵活方便, 只要有需要的时候才会申请空间
 * 缺点: 除了要存储元素外, 还需要额外存储指针(引用)信息
 * @param <T>
 */
class Node<T> {
    T data;
    Node<T> next;
}

class LinkedListStack<T> {
    private Node<T> pHead;

    public LinkedListStack() {
        pHead = new Node<T>();
        pHead.data = null;
        pHead.next = null;
    }

    public int size() {
        int size = 0;
        Node<T> cur = pHead.next;

        while (cur != null) {
            cur = cur.next;
            size++;
        }
        return size;
    }


    public T pop() {
        Node<T> popNode = pHead.next;
        if (popNode == null) return null;
        pHead.next = popNode.next;
        return popNode.data;
    }

    public T top() {
        Node<T> topNode = pHead.next;
        if (topNode == null) return null;
        return topNode.data;
    }

    public void push(T e) {
        Node<T> tlNode = new Node<>();
        tlNode.data = e;
        tlNode.next = pHead.next;
        pHead.next = tlNode;
    }

    public boolean isEmpty() {
        return pHead.next == null;
    }


}
/////////////////////链表