力扣150题（逆波兰式，栈）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

150.根据 逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

1. 本来看题目说每个操作对象可以是另一个逆波兰表达式，想着应该先遍历一遍字符串数组，然后先计算数组中每个是逆波兰式的字符串，然后再计算整个字符串数组表示的逆波兰式。但是看题目所给的测试用例中，字符串数组中的字符串都是单个字符的，看别人的题解也没有对字符串数组中的元素是逆波兰式的情况进行处理，所以该题目其实应该当做计算一次逆波兰式即可。
2. 计算一次逆波兰式的话就比较简单了，就是利用一个栈，遍历一下字符串数组，遇到数字就入栈，遇到运算符就出栈两个字符进行计算，这里要注意先出栈的元素是第二个运算数字；然后将计算结果重新压入栈中，再接着遍历字符串数组，最后留在栈里的元素就是运算结果了。
3. 由于这里是字符串数组，C语言中字符串之间的比较不能用逻辑运算符==来判断，因此遍历字符串的时候判断是否是运算符需要用到库函数strmp，要注意该函数的返回结果代表是什么意思，自己在这就理所当然的以为相等返回1，不等返回0，导致了错误。

4. 还有当遇到数字的时候需要入栈，由于我们遍历的是字符串数组，得到的每个元素是字符串，所以还需要用到库函数atoi，能够将一个字符串转换成数字。

5. 看到评论区中别人发的题解，有人在遍历字符串数组时，不是判断是否是运算符，而是判断是否是数字，这种方法也是可以的，不过要利用到库函数isdigit函数来判断是否是数字。

6. 最后附上调试时的完整代码，顺带复习了一下如何创建二维字符数组，由于二维字符数组中每个元素是一个字符串，因此可以定义一个字符指针数组，然后给这个字符指针数组赋值上初始值。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int evalRPN(char ** tokens, int tokensSize){
    int *stack = malloc(sizeof(int) * tokensSize);
    int top = -1;
    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 = stack[top--];
            int num1 = stack[top--];
            if (strcmp(tokens[i], "+") == 0)
                stack[++top] = num1 + num2;
            if (strcmp(tokens[i], "-") == 0)
                stack[++top] = num1 - num2;
            if (strcmp(tokens[i], "*") == 0)
                stack[++top] = num1 * num2;
            if (strcmp(tokens[i], "/") == 0)
                stack[++top] = num1 / num2;
        } else {
            stack[++top] = atoi(tokens[i]);
        }
    }
    return stack[top];
}
int main()
{
    char *tokens[5] = {"2","1","+","3","*"};
    int a = evalRPN(tokens, 5);
    printf("%d",a);
    return 0;
}