逆波兰表达式求值

C 解法, 执行用时: 3ms, 内存消耗: 668KB, 提交时间: 2022-02-08

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param tokens string字符串一维数组 
 * @param tokensLen int tokens数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    
    int stack[tokensLen];
    int top = -1;
    int i = 0;
    int num1,num2;
    
    //若是运算符，运算
    for(i=0;i<tokensLen;i++){
        
    
    
    if((tokens[i][0]=='+' || tokens[i][0]=='-' || tokens[i][0]=='*' || tokens[i][0]=='/') && strlen(tokens[i])==1){
        switch(tokens[i][0]){
            case '+':
                num1 = stack[top--];
                num2 = stack[top--];
                stack[++top] = num2+num1;
                break;
            
            case '-':
                num1 = stack[top--];
                num2 = stack[top--];
                stack[++top] = num2-num1;
                break;
                
            case '*':
                num1 = stack[top--];
                num2 = stack[top--];
                stack[++top] = num2*num1;
                break;
                
            case '/':
                num1 = stack[top--];
                num2 = stack[top--];
                stack[++top] = num2/num1;
                break;
        }
    }
    
    
    //若是数字，直接入栈
    else{
        stack[++top] = atoi(tokens[i]);
    }
    
    }
    return stack[top];
    
    
}

C 解法, 执行用时: 4ms, 内存消耗: 640KB, 提交时间: 2022-07-31

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param tokens string字符串一维数组 
 * @param tokensLen int tokens数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    int stack[tokensLen];
    int num1=0,num2=0,top=0;
    for(int i=0;i<tokensLen;i++)
    {
        if((*tokens[i]=='+'||*tokens[i]=='-'||*tokens[i]=='*'||*tokens[i]=='/') && strlen(tokens[i])==1)
        {
            switch (*tokens[i])
            {
            case '+':
                num1=stack[top--];
                num2=stack[top--];
                stack[++top]=num2+num1;
                break;
            case '-':
                num1=stack[top--];
                num2=stack[top--];
                stack[++top]=num2-num1;
                break;
                 
            case '*':
                num1=stack[top--];
                num2=stack[top--];
                stack[++top]=num2*num1;
                break;
            case '/':
                num1=stack[top--];
                num2=stack[top--];
                stack[++top]=num2/num1;
                break;
            }       
        }
        else
            stack[++top]=atoi(tokens[i]);
    }
    return stack[top];
}

C 解法, 执行用时: 4ms, 内存消耗: 640KB, 提交时间: 2022-07-20

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param tokens string字符串一维数组 
 * @param tokensLen int tokens数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
typedef struct stack{
    int *val;
    int top;
    int capacity;
}ST;
void StackInit(ST *ps)
{
    ps->capacity = 0;
    ps->top = 0;
    ps->val = NULL;
}
void StackPush(ST *ps,int value)
{
    if(ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity==0?4:ps->capacity*2;
        int* tmp = realloc(ps->val,sizeof(int)*newcapacity);
        
        ps->capacity = newcapacity;
        ps->val = tmp;
    }
    ps->val[ps->top] = value;
    ps->top++;
}
int StackPop(ST *ps)
{
    if(ps->top == 0)
    {
        return 0;
    }
    else
    {
        ps->top--;
        return ps->val[ps->top];
    }
}
int StackTop(ST *ps)
{
    if(ps->top == 0)
    {
        return 0;
    }
    else
    {
        return ps->val[ps->top-1];
    }
}
//char* itoa(int value,char*string,int radix);
//int atoi(const char *str) 
int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    ST stack;
    StackInit(&stack);
    char **cur = tokens;
    int tmp1,tmp2,tmp;
    char * tmp_str;
    int i = 0;
    while(i < tokensLen)
    {
        if((*cur[i]=='+'||*cur[i]=='-'||*cur[i]=='/'||*cur[i]=='*') && *(cur[i]+1) == 0)
        {
            tmp1 = StackPop(&stack);
            tmp2 = StackPop(&stack);
            if(*cur[i] == '+')
                tmp = tmp2 + tmp1;
            else if(*cur[i] == '-')
                tmp = tmp2 - tmp1;
            else if (*cur[i] == '*')
                tmp = tmp2 * tmp1;
            else
                tmp = tmp2 / tmp1;
            StackPush(&stack, tmp);
        }
        else
        {
            tmp = atoi(cur[i]);
            StackPush(&stack, tmp);
        }
        i++;
    }
    return StackPop(&stack);
}

C 解法, 执行用时: 4ms, 内存消耗: 640KB, 提交时间: 2022-04-04

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param tokens string字符串一维数组 
 * @param tokensLen int tokens数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    int val1,val2;
    int Stack[10000];
    int top=-1;
    
    for(int i=0; i<tokensLen; i++) {
        if(tokens[i][0] =='+' && tokens[i][1] == '\0') {
            val2 = Stack[top--];
            val1 = Stack[top--];
            Stack[++top] = val1 + val2;
        }
        else if(tokens[i][0] =='-' && tokens[i][1] == '\0') {
            val2 = Stack[top--];
            val1 = Stack[top--];
            Stack[++top] = val1 - val2;           
        }
        else if(tokens[i][0] =='*' && tokens[i][1] == '\0') {
            val2 = Stack[top--];
            val1 = Stack[top--];
            Stack[++top] = val1 * val2;            
        }
        else if(tokens[i][0] =='/' && tokens[i][1] == '\0') {
            val2 = Stack[top--];
            val1 = Stack[top--];
            Stack[++top] = val1 / val2;             
        }
        else Stack[++top] = atoi(tokens[i]);
    }
    return (int)Stack[top];
}

C 解法, 执行用时: 4ms, 内存消耗: 648KB, 提交时间: 2022-05-19

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param tokens string字符串一维数组 
 * @param tokensLen int tokens数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
#define SIZE 10000

typedef struct{
    int a[SIZE];
    int top;
}Stack;

void push(Stack *s, int num)
{
    if(s->top>=SIZE)
        return;
    else
    {
        s->top++;
        s->a[s->top] = num;
    }
}

int pop(Stack *s)
{
    s->top--;
    return s->a[s->top + 1];
}


int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    char str[10] = {0};
    int num1, num2;
    
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    
    stack->top=-1;
    for(int i=0; i<tokensLen; i++)
    {
        strcpy(str, *tokens);
        if(strcmp(str, "+") == 0)//加法运算
        {
            num2 = pop(stack);
            num1 = pop(stack);
            push(stack, num1+num2);
        }
        else if(strcmp(str, "-") == 0)
        {
            num2 = pop(stack);
            num1 = pop(stack);
            push(stack, num1-num2);
        }
        else if(strcmp(str, "*") == 0)
        {
            num2 = pop(stack);
            num1 = pop(stack);
            push(stack, num1*num2);
        }
        else if(strcmp(str, "/") == 0)
        {
            num2 = pop(stack);
            num1 = pop(stack);
            push(stack, num1/num2);
        }
        else
        {
            num1 = atoi(str);
            push(stack, num1);
        }
        tokens++;
    }
    
    return pop(stack);
    
}

详情