leetcode刷题（4）

ゞ浴缸里的玫瑰 2023-09-25 23:32 66阅读 0赞

各位朋友们，大家好。这两天我将为大家分享我在学习栈的过程中遇到的题目，我们一起来看看。

#### 文章目录 ####

*  逆波兰表达式求值
 *   *  题目要求
     *  用例输入
     *  提示
     *  做题思路
     *  代码实现
     *   *  c语言实现代码
         *  Java语言实现代码
 *  有效的括号
 *   *  Java代码实现

## 逆波兰表达式求值 ##

[leetcode之逆波兰表达式求值（难度：中等）][leetcode]

### 题目要求 ###

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 ‘+’、‘-’、‘\*’ 和 ‘/’ 。  
每个操作数（运算对象）都可以是一个整数或者另一个表达式。  
两个整数之间的除法总是 向零截断 。  
表达式中不含除零运算。  
输入是一个根据逆波兰表示法表示的算术表达式。  
答案及所有中间计算结果可以用 32 位 整数表示。

### 用例输入 ###

示例 1：  
输入：tokens = \[“2”,“1”,“+”,“3”,“\*”\]  
输出：9  
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) \* 3) = 9

示例 2：  
输入：tokens = \[“4”,“13”,“5”,“/”,“+”\]  
输出：6  
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：  
输入：tokens = \[“10”,“6”,“9”,“3”,“+”,“-11”,“*“,”/“,”*”,“17”,“+”,“5”,“+”\]  
输出：22  
解释：该算式转化为常见的中缀算术表达式为：  
((10 \* (6 / ((9 + 3) \* -11))) + 17) + 5  
= ((10 \* (6 / (12 \* -11))) + 17) + 5  
= ((10 \* (6 / -132)) + 17) + 5  
= ((10 \* 0) + 17) + 5  
= (0 + 17) + 5  
= 17 + 5  
= 22

### 提示 ###

提示：  
1 <= tokens.length <= 104  
tokens\[i\] 是一个算符（“+”、“-”、“\*” 或 “/”），或是在范围 \[-200, 200\] 内的一个整数

### 做题思路 ###

很多人看到这个题目的时候可能搞不懂这个题目在说什么，什么是逆波兰表达式呢？平常的四则运算我们知道吧，就像这种1 + ( 2 - 3 \* 4 ) / 5 + 6，这种运算符在数字中间的形式叫做中缀表达式，而逆波兰表达式或者说后缀表达式就是运算符在数字的后面。那么我们该怎样做这道题呢？最好的方法就是运用栈这种数据结构来解决，栈有先进后出，一端进出的特性。当我们遇到数字的时候就将数字放进栈中，当遇到运算符的时候我们就从栈顶取出两个数字，第一次从栈顶取出的数字作为运算符的右值，第二次从栈顶取出的数字作为运算符的左值，然后将运算结果再放进栈中，最后返回栈底的数据就是我们想要的结果。

### 代码实现 ###

#### c语言实现代码 ####

int toInt(char* arr)
    {
        
        int flag = 1;
        char* cur = arr;
        if (*cur == '-')
        {
        
            flag = -1;
            cur++;
        }
        if (*cur == '+')
        {
        
            cur++;
        }
        int ret = 0;
        while (*cur != '\0')
        {
        
            ret = ret * 10 + (*cur - '0');
            cur++;
        }
        return ret*flag;
    }
    
    int evalRPN(char** tokens, int tokensSize) {
        
    //因为c语言并没有为我们直接提供栈的函数，所以我们需要自己模拟出来一个栈
        int* arr = (int*)malloc(tokensSize * sizeof(int));
        //tail是栈顶所在的下标
        int tail = 0;
        for (int i = 0; i < tokensSize; i++)
        {
        
            if (strcmp(tokens[i], "+") == 0 || strcmp(tokens[i], "-") == 0
                || strcmp(tokens[i], "*") == 0 || strcmp(tokens[i], "/") == 0)
            {
        
            //从栈顶取出两个数据
                int num2 = arr[--tail];
                int num1 = arr[--tail];
                switch (tokens[i][0])
                {
        
                case '+':
                    arr[tail++] = num1 + num2;
                    break;
                case '-':
                    arr[tail++] = num1 - num2;
                    break;
                case '*':
                    arr[tail++] = num1 * num2;
                    break;
                case '/':
                    arr[tail++] = num1 / num2;
                    break;
                }
            }
            else
            {
        
            //因为传进来的是字符串数组，所以我们需要将字符串转换为整数，
            //这里是我自己实现的，你也可以使用c语言提供的atoi函数将字符串转化为整数
                int ret = toInt(tokens[i]);
                arr[tail++] = ret;
            }
        }
        return arr[tail-1];
    }

![在这里插入图片描述][3e831d10bf0c4f6594e93e9e71f9f98a.png]

[不懂atoi函数的可以看看这篇文章][atoi]  
![在这里插入图片描述][60bc558af08d4ae68549e32470b0b199.jpeg_pic_center]

#### Java语言实现代码 ####

class Solution {
        
    //这个方法是判断是否为运算符的
        private boolean isOperation(String x) {
        
            if(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
        
                return true;
            }
            return false;
        }
    
        public int evalRPN(String[] tokens) {
        
            Stack<Integer> stack = new Stack<>();
            for(String x:tokens) {
        
                if(!isOperation(x)) {
        
                    stack.push(Integer.parseInt(x));
                } else {
        
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    switch(x) {
        
                        case "+":
                        stack.push(num1+num2);
                        break;
                        case "-":
                        stack.push(num1-num2);
                        break;
                        case "*":
                        stack.push(num1*num2);
                        break;
                        case "/":
                        stack.push(num1/num2);
                        break;
                    }
                }
            }
            return stack.pop();
        }
    }

![在这里插入图片描述][b4e809bea3f44ab0b3cf3c37e876f878.png]

## 有效的括号 ##

这个是我对上一篇文章的Java代码实现的补充，思路在我的这一片文章中，希望大家可以去看看。  
[leetcode刷题（3）][leetcode_3]

### Java代码实现 ###

class Solution {
        
        public boolean isValid(String s) {
        
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
        
                char ch = s.charAt(i);
                if(ch == '(' || ch == '{' || ch == '[') {
        
                    stack.push(ch);
                } else {
        
                    if(stack.empty()) {
        
                        return false;
                    }
                    char ch2 = stack.peek();
                    if(ch == ')' && ch2 == '(' || ch == ']' && ch2 == '[' || ch == '}' && ch2 == '{') {
        
                        stack.pop();
                    } else {
        
                        return false;
                    }
                }
            }
            if(!stack.empty()) {
        
                return false;
            }
            return true;
        }
    }

![在这里插入图片描述][aa5e663415ca438b937464818840aaad.png]

[leetcode]: https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
[3e831d10bf0c4f6594e93e9e71f9f98a.png]: https://img-blog.csdnimg.cn/3e831d10bf0c4f6594e93e9e71f9f98a.png
[atoi]: https://blog.csdn.net/m0_73888323/article/details/129941005
[60bc558af08d4ae68549e32470b0b199.jpeg_pic_center]: https://img-blog.csdnimg.cn/60bc558af08d4ae68549e32470b0b199.jpeg#pic_center
[b4e809bea3f44ab0b3cf3c37e876f878.png]: https://img-blog.csdnimg.cn/b4e809bea3f44ab0b3cf3c37e876f878.png
[leetcode_3]: https://blog.csdn.net/m0_73888323/article/details/130030612
[aa5e663415ca438b937464818840aaad.png]: https://img-blog.csdnimg.cn/aa5e663415ca438b937464818840aaad.png