282. 給表達式添加運算符
給定一個僅包含數字 0-9 的字符串 num 和一個目標值整數 target ，在 num 的數字之間添加 二元 運算符（不是一元）+、- 或 * ，返回所有能夠得到目標值的表達式。
示例 1:輸入: num = "123", target = 6
輸出: ["1+2+3", "1*2*3"] 示例 2:輸入: num = "232", target = 8
輸出: ["2*3+2", "2+3*2"]示例 3:輸入: num = "105", target = 5
輸出: ["1*0+5","10-5"]示例 4:輸入: num = "00", target = 0
輸出: ["0+0", "0-0", "0*0"]示例 5:輸入: num = "3456237490", target = 9191
輸出: []
解題思路
- 使用遞歸的方法，生成所有可能產生的表達式
- 利用基本計算器的代碼，計算出所有表達式的值，找出滿足題意的表達式
代碼
class Solution {List<String> res=new ArrayList<>();int t;public List<String> addOperators(String num, int target) {t=target;int c=0;for (int i=0;i<num.length()-1;i++){c=(c*10)+num.charAt(i)-'0';operator(num,i+1,""+c);if (i==0&&num.charAt(i)=='0')break;}if(num.equals(""+target))res.add(num);return res;} public long calculate(String s) {Stack<Long> stack=new Stack<>();Stack<Long> characterStack=new Stack<>();int n=s.length();int i = 0,sign=1,cur=0;while ( i < n) {char c = s.charAt(i);if(c==' '){i++;continue;}if(Character.isDigit(c)){long sum=0;while (i < n&&Character.isDigit(s.charAt(i))){sum*=10;sum+=s.charAt(i)-'0';i++;}stack.push(sum);i--;}else {if(c=='+'||c=='-'){if(!characterStack.isEmpty()){stack.push(stack.pop()*characterStack.pop()+stack.pop());}characterStack.push(c=='+'?1L:-1L);}else{int sum=0;i++;while (s.charAt(i)==' ') i++;while (i < n&&Character.isDigit(s.charAt(i))){sum*=10;sum+=s.charAt(i)-'0';i++;}if(c=='*')stack.push(stack.pop()*sum);elsestack.push(stack.pop()/sum);i--;}}i++;}return stack.size()==1?stack.pop():stack.pop()*characterStack.pop()+stack.pop();}public void operator(String num, int s,String sb) {if (s==num.length()){if (calculate(sb)==t)res.add(sb);return;}int c=0;for (int i=s;i<num.length();i++){c=(c*10)+num.charAt(i)-'0';operator(num,i+1,sb+"+"+c);operator(num,i+1,sb+"-"+c);operator(num,i+1,sb+"*"+c);if (i==s&&num.charAt(i)=='0')break;}}
}
)
)
