逆波兰表达式求值
题目要求
给你一个字符串数组 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]; }
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代码实现的补充，思路在我的这一片文章中，希望大家可以去看看。
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; } }
