leetcode刷题（4）

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

文章目录

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

        逆波兰表达式求值

        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 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