选自 leetcode basic calculator
- Version 1: Support [ + - ]
- (not tested)
- class Solution {
- public int calculate(String s) {
- int len = s.length(), sign = 1, res = 0, num = 0;
- for (int i = 0; i <len; i++) {
- char c = s.charAt(i);
- if (c == ' ') continue;
- if (Character.isDigit(c)) {
- num = num * 10 + c - '0';
- if (i == len - 1 || !Character.isDigit(s.charAt(i + 1))) { // 当后一位不是数字时就停止并且 reset
- res += sign * num;
- num = 0;
- }
- } else { // + or -
- if (c == '+') sign = 1; // 记录之前的状态, 因为数字是一个位一个位
- if (c == '-') sign = -1;
- }
- }
- return res;
- }
- }
- Version 2: Support [ + - ( ) ] (this problem)
- class Solution {
- public int calculate(String s) {
- int len = s.length(), sign = 1, res = 0, num = 0;
- Stack<Integer> stack = new Stack<>();
- for (int i = 0; i <len; i++) {
- char c = s.charAt(i);
- if (c == ' ') continue; // 只要数字不会被拆开, 用这个就没问题.
- if (Character.isDigit(c)) {
- num = num * 10 + c - '0';
- if (i == len - 1 || !Character.isDigit(s.charAt(i + 1))) {
- res += sign * num;
- num = 0;
- }
- } else { // + - ( )
- if (c == '+') {
- sign = 1;
- }
- if (c == '-') {
- sign = -1;
- }
- if (c == '(') {
- stack.push(res);
- stack.push(sign);
- res = 0;
- sign = 1;
- }
- if (c == ')') {
- res = res * stack.pop() + stack.pop(); // 现在的和 sign + 之前的
- }
- }
- }
- return res;
- }
- }
- Version 3: Support [ + - */ ]
- class Solution {
- public int calculate(String s) {
- if (s == null || s.length() == 0) return 0;
- int len = s.length();
- int num = 0;
- char sign = '+';
- int curr = 0, res = 0; //important, use curr to store value of last segment.
- for (int i = 0; i < len; i++) {
- if (s.charAt(i) == ' ') continue;
- if (!Character.isDigit(s.charAt(i))) {
- num = 0;
- sign = s.charAt(i);
- if (sign == '+' || sign == '-') {
- res += curr;
- curr = 0; // not necessary
- }
- } else {
- num = num * 10 + s.charAt(i) - '0';
- if (i == len - 1 || !Character.isDigit(s.charAt(i + 1))) {
- if (sign == '+') curr = num;
- if (sign == '-') curr = -num;
- if (sign == '*') curr *= num;
- if (sign == '/') curr /= num;
- }
- }
- }
- res += curr; // add last segment
- return res;
- }
- }
- Version 4: Support [ + - */ ( ) ]
Should be easily derived from Version 6, just remove anything related to ^.
- Version 5: Support [ + - */ ^ ]
- class Solution {
- public int calculate(String s) {
- // remove spaces // 这部分也可以放在下面判断, 一句搞定, 是空格的时候跳过
- String[] strs = s.split(" ");
- StringBuilder sb = new StringBuilder();
- for (int i = 0; i < strs.length; i++) {
- sb.append(strs[i]);
- }
- s = sb.toString();
- // init
- if (s == null || sb.length() == 0) return 0;
- int num = 0;
- Stack<Integer> numStack = new Stack<>();
- Stack<Character> opStack = new Stack<>();
- Map<Character, Integer> map = new HashMap<>();
- map.put('+', 1); map.put('-', 1);
- map.put('*', 2); map.put('/', 2);
- map.put('^', 3);
- for (int i = 0; i <s.length(); i++) {
- char c = s.charAt(i);
- if (Character.isDigit(c)) {
- num = num * 10 + c - '0';
- if (i == s.length() - 1 || !Character.isDigit(s.charAt(i + 1))) {
- numStack.push(num);
- num = 0;
- }
- } else { // op: + - */ ^
- if (opStack.empty() || map.get(c)> map.get(opStack.peek())) {
- opStack.push(c);
- } else {
- while (!opStack.empty() && map.get(c) <= map.get(opStack.peek())) {
- helper(numStack, opStack);
- }
- opStack.push(c);
- }
- }
- }
- while (!opStack.empty()) {
- helper(numStack, opStack);
- }
- return numStack.pop();
- }
- private void helper(Stack<Integer> numStack, Stack<Character> opStack) {
- int b = numStack.pop();
- int a = numStack.pop();
- char op = opStack.pop();
- if (op == '+') numStack.push(a + b);
- if (op == '-') numStack.push(a - b);
- if (op == '*') numStack.push(a * b);
- if (op == '/') numStack.push(a / b);
- if (op == '^') numStack.push((int)Math.pow(a, b));
- }
- }
- Version 6: Support [ + - */ ^ ( ) ]
- class Solution {
- public int calculate(String s) {
- // remove spaces // 这部分也可以放在下面判断, 一句搞定, 是空格的时候跳过
- String[] strs = s.split(" ");
- StringBuilder sb = new StringBuilder();
- for (int i = 0; i <strs.length; i++) {
- sb.append(strs[i]);
- }
- s = sb.toString();
- // init
- if (s == null || sb.length() == 0) return 0;
- int num = 0;
- Stack<Integer> numStack = new Stack<>();
- Stack<Character> opStack = new Stack<>();
- Map<Character, Integer> map = new HashMap<>();
- map.put('+', 1); map.put('-', 1);
- map.put('*', 2); map.put('/', 2);
- map.put('^', 3);
- for (int i = 0; i <s.length(); i++) {
- char c = s.charAt(i);
- if (Character.isDigit(c)) {
- num = num * 10 + c - '0';
- if (i == s.length() - 1 || !Character.isDigit(s.charAt(i + 1))) {
- numStack.push(num);
- num = 0;
- }
- } else { // op or ()
- if (c == '(') {
- opStack.push(c);
- }
- if (c == ')') {
- while (!opStack.empty() && opStack.peek() != '(') {
- helper(numStack, opStack);
- }
- opStack.pop(); // pop the '('
- }
- if (map.containsKey(c)) { // + - */ ^
- if (opStack.empty() || opStack.peek() == '(' || map.get(c)> map.get(opStack.peek())) {
- opStack.push(c);
- } else {
- while (!opStack.empty() && opStack.peek() != '(' && map.get(c) <= map.get(opStack.peek())) {
- helper(numStack, opStack);
- }
- opStack.push(c);
- }
- }
- }
- }
- while (!opStack.empty()) {
- helper(numStack, opStack);
- }
- return numStack.pop();
- }
- private void helper(Stack<Integer> numStack, Stack<Character> opStack) {
- int b = numStack.pop();
- int a = numStack.pop();
- char op = opStack.pop();
- if (op == '+') numStack.push(a + b);
- if (op == '-') numStack.push(a - b);
- if (op == '*') numStack.push(a * b);
- if (op == '/') numStack.push(a / b);
- if (op == '^') numStack.push((int)Math.pow(a, b));
- }
- }
来源: http://www.bubuko.com/infodetail-3375011.html