150_逆波蘭表達式求值

150_逆波蘭表達式求值

package 棧;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
 * @author Huangyujun
 *
 * 字尾表達式：
 * 從左至右掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（次頂元素 op 棧頂元素），
 * 并将結果入棧；重複上述過程直到表達式最右端，最後運算得出的值即為表達式的結果
 */

/**
 * 題意：給的逆波蘭表達式就隻有 數字和運算符呀，
 * 是以自己寫一個方法判斷是否非數字即可呀
 * @author Huangyujun
 *
 */
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}

//public class _150_逆波蘭表達式求值 {
//    public int evalRPN(String[] tokens) {
//        Stack<String> num_stack = new Stack<String>();
//        Stack<String> opt_stack = new Stack<String>();
////        int state = 0;
////        final int num_state = 1;
////        final int opt_state = 2;
//        String[] nums = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
////        String[] opts = {"+", "-", "*", "/"};
//        //因為題意給的是合法的表達式：（一開始先遇到的是數字, 但是後邊突然是字元串呀，是以需要修改一下判斷條件）
//        //使用char 判斷吧
//        for(int i = 0; i < tokens.length; i++) {
////            for(String num : nums) {
////                if(tokens[i].equals(num)) {    //某個數字
////                    num_stack.push(tokens[i]);
//////                    state = num_state;
////                    break;
////                }
////            }
//            //這個判斷條件不對，因為數字可能有負數，超過 0 到 9 的數呀
//            if(nums[0].equals(tokens[i]) || nums[1].equals(tokens[i]) || nums[2].equals(tokens[i]) ||
//                    nums[3].equals(tokens[i]) || nums[4].equals(tokens[i]) || nums[5].equals(tokens[i]) ||
//                    nums[6].equals(tokens[i]) || nums[7].equals(tokens[i]) || nums[8].equals(tokens[i]) ||
//                    nums[9].equals(tokens[i]) ) {
//                num_stack.push(tokens[i]);
//            }else {
//                opt_stack.push(tokens[i]);    //題意提示總是有效了
//                   if(num_stack.size() < 2) {
//                       continue;
//                   }else {
//                       int num2 = Integer.parseInt(num_stack.pop());
//                       int num1 = Integer.parseInt(num_stack.pop());
//                       String opt = opt_stack.pop();
//                       if(opt.equals("+")) {
//                           num_stack.push(Integer.toString(num1 + num2));
//                       }else if(opt.equals("-")) {
//                           num_stack.push(Integer.toString(num1 - num2));
//                       }else if(opt.equals("*")) {
//                           num_stack.push(Integer.toString(num1 * num2));
//                       }else {
//                           num_stack.push(Integer.toString(num1 / num2));
//                       }
//                   }
//            }
//        }
//        return Integer.parseInt(num_stack.peek());
//    }
//}