题解 | 逆波兰表达式求值

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param tokens string字符串一维数组 
 * @param tokensLen int tokens数组长度
 * @return int整型
 */
int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    int number[10000];
    int top=-1;
    int temp=0;
    for(int i=0;i<tokensLen;i++){
        if(*tokens[i]!='+'&&*tokens[i]!='*'&&*tokens[i]!='/'&&*tokens[i]!='-'||(*tokens[i]=='-'&&tokens[i][1]!='\0')){
            top++;
            number[top]=atoi(tokens[i]);
        }
        else{
            if(*tokens[i]=='+'){
                temp=number[top]+number[top-1];
                top--;
                number[top]=temp;
            }
            if(*tokens[i]=='*'){
                temp=number[top]*number[top-1];
                top--;
                number[top]=temp;
            }
            if(*tokens[i]=='-'){
                temp=number[top-1]-number[top];
                top--;
                number[top]=temp;
            }
            if(*tokens[i]=='/'){
                temp=number[top-1]/number[top];
                top--;
                number[top]=temp;
            }
        }
    }
    return number[top];
}

• 定义一个number数组来盛放数字栈，定义栈顶指针top;
• 遍历字符串，当当前是数字时放入数字栈中（注意负数的判定）（注意转换为int类型存放），top指针上移；
• 当遇到符号时，将数字栈中栈顶与其下一个存放的数字进行对应的运算，将两个数字出栈，然后将其运算结果入栈；最后的数字栈栈顶即最后的运算结果
• 使用atoi()函数实现int类型的转换；负数判定为*tokens[i]=='-'&&tokens[i][1]!='\0'即tokens[i][0]=='-'&&tokens[i][1]!='\0'（避免将负数判定为减号与数字）