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

向右看齐 2021-12-20 22:29 238阅读 0赞

## 题目描述： ##

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

示例 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 }

##  ##

转载于:https://www.cnblogs.com/sqchao/p/11074147.html