【Leetcode】Evaluate Reverse Polish Notation JAVA

浏览数：27 / 时间：2015年06月08日

一、问题描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6


二、分析
该问题是其实是一个后缀表达的计算，这道题实现主要有下面几点注意：
　　1、如何将String数组中的操作数与操作符读出来，并加以区分开。
　　2、当读出来的是操作数时，将该操作数放入到堆栈（Stack）中
　　3、当读出来的是操作符时，从堆栈中取出来两个元素并用此操作符进行计算，并将计算的结果放入到堆栈（Stack）中

package com.edu.leetcode;

import java.util.Stack;

public class EvaluateReversePolishNotation {
    
    

    public int evalRPN(String[] tokens) {
        
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for (int i = 0; i < tokens.length; i++) {
            char c = tokens[i].charAt(0);                                          //    将字符串的第一元素取出来
            if (tokens[i].length()!=1||‘0‘ <= c && c <= ‘9‘) {          //判断为操作数的标准：1、当字符串的长度大于2时，必定为数字；2、当长度为1时，如果第一个为整数时；
                stack.push(Integer.valueOf(tokens[i]).intValue());
            } else {
                int twoNumber = stack.pop();                    //取出栈顶元素为第二操作数
                int oneNumber = stack.pop();                    //再取出栈顶元素第一操作数
                switch (c) {                                                //根据操作数，计算结果
                case ‘*‘:
                    result = oneNumber * twoNumber;
                    break;
                case ‘+‘:
                    result = oneNumber + twoNumber;
                    break;
                case ‘-‘:
                    result = oneNumber - twoNumber;
                    break;
                case ‘/‘:
                    if (twoNumber != 0) {
                        result = oneNumber /twoNumber;
                        break;
                    }
                    else{
                        System.out.println("\nDivided by 0!");
                        stack.clear();
                    }
                }
                stack.push(result);         　　//将结果放入到堆栈中
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String[] string = { "0","3","/"};
        EvaluateReversePolishNotation erpn = new EvaluateReversePolishNotation();
        int s = erpn.evalRPN(string);
        System.out.println(s);
    }

}