150. 逆波兰表达式求值
150. 逆波兰表达式求值
题目：
题解：
class Solution { public static boolean isNumeric(String str) { return str != null && str.matches("-?\\d+"); } public int evalRPN(String[] tokens) { //将数字放在一个集合中 List<Integer> list = new ArrayList<>(); for(int i=0;i<tokens.length;i++) { String c = tokens[i]; if(isNumeric(c)) { list.add(Integer.valueOf(c)); } else { Integer a = list.remove(list.size()-1); Integer b = list.remove(list.size()-1); Integer r = 0; if("+".equals(c)) { r = a+b; } else if("-".equals(c)) { r = b-a; } else if("*".equals(c)) { r = b * a; } else { r = (int)b/a; } list.add(r); } } return list.get(0); } }224. 基本计算器
224. 基本计算器
很难，很麻烦，要考虑的东西很多，就像我昨天考的六级一样
题目：
题解：
class Solution { public int calculate(String s) { // 存放所有的数字 Deque<Integer> nums = new ArrayDeque<>(); // 为了防止第一个数为负数，先往 nums 加个 0 nums.addLast(0); // 将所有的空格去掉 s = s.replaceAll(" ", ""); // 存放所有的操作，包括 +/- Deque<Character> ops = new ArrayDeque<>(); int n = s.length(); char[] cs = s.toCharArray(); for (int i = 0; i < n; i++) { char c = cs[i]; if (c == '(') { ops.addLast(c); } else if (c == ')') { // 计算到最近一个左括号为止 while (!ops.isEmpty()) { char op = ops.peekLast(); if (op != '(') { calc(nums, ops); } else { ops.pollLast(); break; } } } else { if (isNum(c)) { int u = 0; int j = i; // 将从 i 位置开始后面的连续数字整体取出，加入 nums while (j < n && isNum(cs[j])) u = u * 10 + (int)(cs[j++] - '0'); nums.addLast(u); i = j - 1; } else { if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) { nums.addLast(0); } // 有一个新操作要入栈时，先把栈内可以算的都算了 while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops); ops.addLast(c); } } } while (!ops.isEmpty()) calc(nums, ops); return nums.peekLast(); } void calc(Deque<Integer> nums, Deque<Character> ops) { if (nums.isEmpty() || nums.size() < 2) return; if (ops.isEmpty()) return; int b = nums.pollLast(), a = nums.pollLast(); char op = ops.pollLast(); nums.addLast(op == '+' ? a + b : a - b); } boolean isNum(char c) { return Character.isDigit(c); } }
