【栈】逆波兰表达式求解

做题思路：用栈解决

• 当字符串中为数字，将数字压入栈中
• 若为符号，将栈顶的两个数字出栈，进行运算，然后将新数字入栈

//这里一定要注意判断整个字符串，因为如果单独判断第一个字符会发现有些负数的第一个字符也是'-'。无法确定字符串是一个符号还是数字
int isSign(char* token) {
    return strcmp(token, "+") == 0 || strcmp(token, "/") == 0 || strcmp(token, "-") == 0 || strcmp(token, "*") == 0;
}

int convertToNum(char* string) {
    //符号位，0为正，1为负
    int sign = 0;
    int num = 0;
    if(*string == '-' || *string == '+') {
        if(*string == '-')
            sign = 1;
        string++;
    }
    while(*string != '\\0') {
        int digit = *string - '0';
        num = num * 10 + digit;
        string++;
    }
    if(sign)
        num = -num;
    return num;
}

int evalRPN(char ** tokens, int tokensSize){
    int stack[5000];
    int stack_top = 0;

    int i;
    for(i = 0; i < tokensSize; i++) {
        //如果是符号，弹出栈顶两个元素
        if(isSign(tokens[i])) {
            int num1 = stack[--stack_top];
            int num2 = stack[--stack_top];
            int num3;

            switch(*(tokens[i])) {
                case '+':
                    num3 = num2 + num1;
                    break;
                case '-':
                    num3 = num2 - num1;
                    break;
                case '*':
                    num3 = num2 * num1;
                    break;
                case '/':
                    num3 = num2 / num1;
                    break;
            }
            stack[stack_top++] = num3;
        }
        //如果是数字，入栈
        else {
            stack[stack_top++] = convertToNum(tokens[i]);
        }
    }
    return stack[--stack_top];
}