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

逆波兰表达式求值

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

题目要求

给你一个字符串数组 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];
}

不懂atoi函数的可以看看这篇文章

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();}
}

有效的括号

这个是我对上一篇文章的Java代码实现的补充，思路在我的这一片文章中，希望大家可以去看看。
leedcode刷题（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;}
}