本文主要是介绍Basic Calculator 总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Basic Calculator
思路：stack中间存数,遇见+,-都当符号位，push num或者-num进去；最后相加；重要的是如何处理括号，那么这里一种方法是用递归调用；count左右括号，如果为0，那么就是一个反括号的位置了，那么
//( )
//j......i;
substring(j + 1, i);
这题的通用解法，可以扩展到二三题；
class Solution {public int calculate(String s) {if(s == null || s.length() == 0) {return 0;}int len = s.length();int res = 0;int num = 0;char sign = '+';Stack<Integer> stack = new Stack<>();for(int i = 0; i < len; i++) {char c = s.charAt(i);if(Character.isDigit(c)) {num = num * 10 + c - '0';}// ();// 每次是得到当前的运算符，计算之前的数和运算符，然后更新sign为当前的运算符；// 注意最后一个数字，由于符号总是在数字之前，所以最后一个数字没有办法计算，要单独列出来；if(!Character.isDigit(c) && (c != ' ') || i == len - 1) {if(c == '(') {int j = i; int count = 0;for(; i < len; i++) {if(s.charAt(i) == '(') {count++;}if(s.charAt(i) == ')') {count--;}if(count == 0) {break;}}//找到对应的反括号的位置；递归调用计算即可；//( )//j......i;num = calculate(s.substring(j + 1, i));}if(sign == '+') {stack.push(num);} else if(sign == '-') {stack.push(-num);}sign = c;num = 0;}}for(int val : stack) {res += val;}return res;}
}Basic Calculator II
思路：这题跟上题不一样的地方在于有了乘法和除法。这样的话，当前的数就要跟前面一个数发生关系，使用了一个stack来保存数字。通过栈来实现运算，按顺序读取字符串，将第一个数入栈。之后遇到+，将下一个数+num入栈；遇到-，则将-num入栈；遇到乘或除，先将上一个数出栈，与当前数进行运算后，再将结果入栈。读取完整个字符串后，将栈中所有的数相加即运算结果。
// 每次是得到当前的运算符，计算之前的数和运算符，然后更新sign为当前的运算符；
// 注意最后一个数字，由于符号总是在数字之前，所以最后一个数字没有办法计算，要单独列出来；
class Solution {public int calculate(String s) {if(s == null || s.length() == 0) {return 0;}char sign = '+';Stack<Integer> stack = new Stack<>();int num = 0;int len = s.length();for(int i = 0; i < len; i++) {// 取数；char c = s.charAt(i);if(Character.isDigit(c)) {num = num * 10 + c - '0';}// 每次是得到当前的运算符，计算之前的数和运算符，然后更新sign为当前的运算符；// 注意最后一个数字，由于符号总是在数字之前，所以最后一个数字没有办法计算，要单独列出来；if(!Character.isDigit(c) && c != ' ' || i == len - 1) {if(sign == '+') {stack.push(num);} else if(sign == '-') {stack.push(-num);} else if(sign == '*') {stack.push(stack.pop() * num);} else if(sign == '/') {stack.push(stack.pop() / num);}sign = c;num = 0;}}int res = 0;for(int val : stack) {res += val;}return res;}
}Basic Calculator III 这里跟calculator II很类似，不同的就是加入了括号，括号的处理可以用递归，找到左右边界，递归算出num；每次是得到当前的运算符，计算之前的数和运算符，然后更新sign为当前的运算符；其余的跟calculator II一模一样，都是把值算好了，丢到stack里面，最后把stack里面的东西sum起来就是答案；中间找左右两个边界的，跟 1087 Brace Expansion 很类似；
class Solution {public int calculate(String s) {if(s == null || s.length() == 0) {return 0;}Stack<Integer> stack = new Stack<Integer>();int number = 0;char sign = '+';for(int i = 0; i < s.length(); i++) {char c = s.charAt(i);if(Character.isDigit(c)) {number = number * 10 + c - '0';} if(!Character.isDigit(c) && c != ' ' || i == s.length() - 1){if(c == '(') {int j = i;int count = 0;while(i < s.length()) {if(s.charAt(i) == '(') {count++;} else if(s.charAt(i) == ')') {count--;}if(count == 0) {break;}i++;}number = calculate(s.substring(j + 1, i));}if(sign == '+') {stack.push(number);} else if(sign == '-') {stack.push(-number);} else if(sign == '*') {stack.push(stack.pop() * number);} else if(sign == '/') {stack.push(stack.pop() / number);}sign = c;number = 0;}}int res = 0;while(!stack.isEmpty()) {res += stack.pop();}return res;}
}Brace Expansion, 也是找到左右边界，split出来，然后做backtracking。
class Solution {public String[] expand(String s) {List<String> list = new ArrayList<>();StringBuilder sb = new StringBuilder();dfs(s, 0, sb, list);Collections.sort(list);String[] res = new String[list.size()];for(int i = 0; i < res.length; i++) {res[i] = list.get(i);}return res;}private void dfs(String s, int index, StringBuilder sb, List<String> list) {if(index == s.length()) {list.add(new String(sb.toString()));return;}char c = s.charAt(index);if(c == '{') {int j = index;while(index < s.length() && s.charAt(index) != '}') {index++;}// j....index;// { };String[] splits = s.substring(j + 1, index).split(",");for(String split: splits) {sb.append(split);dfs(s, index + 1, sb, list);sb.setLength(sb.length() - split.length());}} else {sb.append(c);dfs(s, index + 1, sb, list);sb.deleteCharAt(sb.length() - 1);}}
}这篇关于Basic Calculator 总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
