Expression evaluation
use stack
- Basic calculator
public int calculate(String s) { if (s == null || s.length() == 0) { return -1; } Stack<Integer> stack = new Stack<>(); int op = 1; int num = 0; int res = 0; int i = 0; while (i < s.length()) { char c = s.charAt(i); if (Character.isDigit(c)) { while (i < s.length() && Character.isDigit(s.charAt(i))) { num = num 10 + s.charAt(i) - '0'; i++; } res += num op; } else if (c == '+') { op = 1; num = 0; i++; } else if (c == '-') { op = -1; num = 0; i++; } else if (c == '(') { stack.push(res); stack.push(op); res = 0; op = 1; i++; } else if (c == ')') { op = stack.pop(); num = stack.pop(); res = num + res * op; i++; } else { i++; } } return res; }
- Basic calculator II
public int calculate(String s) { if (s == null || s.length() == 0) { return 0; } Stack<Integer> stack = new Stack<>(); int op = 0, num = 0; int res = 0; int i = 0; while (i < s.length()) { char c = s.charAt(i); if (Character.isDigit(c)) { num = num 10 + s.charAt(i) - '0'; i++; } if (op == 3 || op == 4) { int t = stack.pop(); if (op == 3) res = t num; else res = t / num; stack.push(res); } else stack.push(num); } else if (c == '+') { op = 1; stack.push(op); num = 0; i++; } else if (c == '-') { op = 2; stack.push(op); num = 0; i++; } else if (c == '*') { op = 3; num = 0; i++; } else if (c == '/') { op = 4; num = 0; i++; } else { i++; } } res = 0; while (stack.size() > 1) { int a = stack.pop(); op = stack.pop(); res = op == 1 ? res + a : res - a; } res += stack.pop(); return res; }
- Evaluate Reverse Polish Notation
public int evalRPN(String[] tokens) { if (tokens == null || tokens.length == 0) { return 0; } Stack<Integer> stack = new Stack<>(); for (int i = 0; i < tokens.length; i++) { String s = tokens[i]; if (s.equals("+") || s.equals("-") || s.equals("") || s.equals("/")) { int b = stack.pop(); int a = stack.pop(); stack.push(evaluate(a, b, s)); } else { stack.push(Integer.parseInt(s)); } } return stack.pop(); } public int evaluate(int a, int b, String token) { switch (token) { case "+" : return a + b; case "-" : return a - b; case "" : return a * b; case "/" : return a / b; default : return 0; } }
- Expression Add Operators: add operators to a string of numbers
public List<String> addOperators(String num, int target) { List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); dfs(res, sb, num, 0, target, 0, 0); return res; } public void dfs(List<String> res, StringBuilder sb, String num, int pos, int target, long prev, long multi) { if(pos == num.length()) { if(target == prev) res.add(sb.toString()); return; } for(int i = pos; i < num.length(); i++) { if(num.charAt(pos) == '0' && i != pos) break; long curr = Long.parseLong(num.substring(pos, i + 1)); int len = sb.length(); if(pos == 0) { dfs(res, sb.append(curr), num, i + 1, target, curr, curr); sb.setLength(len); } else { dfs(res, sb.append("+").append(curr), num, i + 1, target, prev + curr, curr); sb.setLength(len); dfs(res, sb.append("-").append(curr), num, i + 1, target, prev - curr, -curr); sb.setLength(len); dfs(res, sb.append("").append(curr), num, i + 1, target, prev - multi + multi curr, multi * curr); sb.setLength(len); } } }
- Different Ways to Add Parentheses:
divide into left and right half and recursively solve
public List<Integer> diffWaysToCompute(String input) { List<Integer> res = new ArrayList<>(); if (input.length() == 0) { return res; } for (int i = 0; i < input.length(); i++) { char c = input.charAt(i); if (c == '+' || c == '-' || c == '') { String left = input.substring(0, i); String right = input.substring(i+1); List<Integer> l = diffWaysToCompute(left); List<Integer> r = diffWaysToCompute(right); for (int a : l) { for (int b : r) { res.add(eval(a, b, c)); } } } } if (res.size() == 0) { res.add(Integer.parseInt(input)); } return res; } public int eval(int a, int b, char c) { switch(c) { case '+' : return a + b; case '-' : return a - b; case '' : return a * b; default : return -1; } }