算法刷题笔记-stack-四则运算

sqchao 2019-06-23 原文

算法刷题笔记-stack-四则运算

题目描述：

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, – 以及 * 。

示例 1:

输入: “2-1-1”
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses

解题思路：

　　1、每次仅运算乘除，将运算结果入栈，

　　　　a、保留前一个运算符

　　　　b、如果前一个运算符是乘除，弹出一个数字，与当前运算，结果回送。

　　　　c、如果是减号，将当前数字取负，送进堆栈；正号，直接入栈

　　2、扫描结束后，对栈中所有元素求和。结束

java语言实现：

 1 class Solution {
 2     public static int calculate(String s) {
 3         int res = 0;
 4         int num = 0;
 5         char sign = '+';
 6         Stack<Integer> stack = new Stack<>();
 7         char[] sarr = s.toCharArray();
 8         for (int i = 0; i < sarr.length; i++) {
 9             if (sarr[i] >= '0') {
10                 num = num * 10 + sarr[i] - '0'; // 注意字符变成数字，方可参加运算，否则直接ASCII码参与运算，出错。
11             }
12             if ((sarr[i] < '0' && sarr[i] != ' ') || i == sarr.length - 1) {
13                 if (sign == '+') {
14                     stack.push(num);
15                 } else if (sign == '-') {
16                     stack.push(-num);
17                 } else if (sign == '*' || sign == '/') {
18                     int top = stack.pop();
19                     stack.push(sign == '*' ? top * num : top / num);
20                 }
21                 sign = sarr[i];
22                 num = 0;
23             }
24         }
25         while (!stack.isEmpty()) {
26             res += stack.pop();
27         }
28         return res;
29     }
30 
31     public static int calculate2(String s) {
32     　　 s=s.trim();  //清洗输入数据，并记得将洗过的数据回送给s
33         java.util.Stack<Integer> stack = new java.util.Stack<>();
34 //        String[] nums=s.split("[-+/*]");
35         int left_number=0;
36         char fuhao_before='+';  //保存前一个符号
37         char fuhao;
38         for (int i=0;i<s.length();i++){
39             if (Character.isDigit(s.charAt(i))){
40                 left_number=left_number*10+s.charAt(i)-'0';
41 
42             }if(i==s.length()-1 || ! Character.isDigit(s.charAt(i))){
43                 fuhao=s.charAt(i);
44                 switch (fuhao_before){
45                     case '+':
46                         stack.push(left_number);
47                         fuhao_before=fuhao;
48                         break;
49                     case '-':
50                         stack.push(-left_number);
51                         fuhao_before=fuhao;
52                         break;
53                     case '*':
54                         stack.push(stack.pop()*left_number);  //其实是右边的数
55                         fuhao_before=fuhao;
56                         break;
57                     case '/':
58                         stack.push(stack.pop()/left_number);
59                         fuhao_before=fuhao;
60                         break;
61                     default:
62                         break;
63 
64                 }
65                 left_number=0; //归零
66             }
67         }
68 
69         int result=0;
70         while (! stack.empty()){
71             result+=stack.pop();
72 
73         }
74         return result;
75     }
76 }