首页 > 试题广场 >

逆波兰表达式求值

[编程题]逆波兰表达式求值
  • 热度指数：36524 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个逆波兰表达式，求表达式的值。

数据范围：表达式长度满足 ，表达式中仅包含数字和 + ，- , * , / ，其中数字的大小满足 。
示例1

输入

["2","1","+","4","*"]

输出

12
示例2

输入

["2","0","+"]

输出

2
算法知识视频讲解
添加回答
C
cs小白_头像 cs小白_ 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param tokens string字符串一维数组 
 * @param tokensLen int tokens数组长度
 * @return int整型
 */
#include <stdio.h>
int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    int n[10000]={0},top=-1,i,j,k,l,a,b,m=0;
    
    
    
    
    for(i=0;i<tokensLen;i++){
        
        if(**(tokens+i)=='+'){
            b=n[top--];
            a=n[top--];
            n[++top]=(a+b);
            continue;
        }
        if((**(tokens+i)=='-')&&*(*(tokens+i)+1)=='\0'){
            b=n[top--];
            a=n[top--];
            n[++top]=(a-b);
            continue;
        }
        if(**(tokens+i)=='*'){
            b=n[top--];
            a=n[top--];
            n[++top]=(a*b);
            continue;
        }
        if(**(tokens+i)=='/'){
            b=n[top--];
            a=n[top--];
            n[++top]=(a/b);
            continue;
        }
        if(**(tokens+i)>='0'&&**(tokens+i)<='9'){
              //k=sizeof(*(tokens+i))/;
              m=0,j=0;
              while(*(*(tokens+i)+j)!='\0') {
                    m=m*10+(*(*(tokens+i)+j)-'0');
                    j++;
              }
              n[++top]=m;
              continue;
        }
        if(**(tokens+i)=='-'&&*(*(tokens+i)+1)!='\0'){
              //k=sizeof(*(tokens+i))/;
              m=0,j=1;
              while(*(*(tokens+i)+j)!='\0') {
                    m=m*10+(*(*(tokens+i)+j)-'0');
                    j++;
              }
              n[++top]=0-m;
              continue;
        }



        printf("%c",**(tokens+i));
    }
    return n[top];
    
}

发表于 2024-11-16 09:03:27 回复(0)
C
小波201712132217124头像 小波201712132217124 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param tokens string字符串一维数组 
 * @param tokensLen int tokens数组长度
 * @return int整型
 */

#include <stdlib.h>
#define MAX_LEN 1000

typedef struct my_stack {
    int data[MAX_LEN];
    int top;
} my_stack;

void init_my_stack(my_stack *s) {
    s->top = -1;   
}

int is_empty(my_stack *s) {
    return s->top == -1;
}

void push(my_stack *s, int val) {
    if (s->top < MAX_LEN-1) {
        s->data[++s->top] = val;
    } else {
        printf("error: stack overflow\n");
    }
}

int top(my_stack *s) {
    if (!is_empty(s)) {
        return s->data[s->top];
    } else {
        return -201;
    }
}

int pop(my_stack *s) {
    if (!is_empty(s)) {
        return s->data[s->top--];
    } else {
        return -201;
    }
}

int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    int tmp=0, num1, num2;
    my_stack *haha = (my_stack *)malloc(sizeof(my_stack));

    init_my_stack(haha);

    for (int i=0; i<tokensLen; i++) {
        if ((tokens[i][0] >= '0' && tokens[i][0] <= '9') || tokens[i][0] == '-') {
            if (tokens[i][0] == '-') {
                if (strlen(tokens[i]) > 1) {   //表示是一个负数
                    for (int j=1; j<strlen(tokens[i]); j++) {
                        tmp = 10 * tmp + (tokens[i][j] - '0');
                    }
                    push(haha, -1*tmp);
                    tmp=0;
                } else {  //是个操作符
                    num1 = pop(haha);
                    num2 = pop(haha);
                    push(haha, num2 - num1);
                } 
            } else {
                for (int j=0; j<strlen(tokens[i]); j++) {
                    tmp = 10 * tmp + (tokens[i][j] - '0');
                }
                push(haha, tmp);
                tmp=0;
            }
        } else if (tokens[i][0] == '+') {
            num1 = pop(haha);
            num2 = pop(haha);
            push(haha, num2+num1);
        } else if (tokens[i][0] == '/') {
            num1 = pop(haha);
            num2 = pop(haha);
            push(haha, num2 / num1);
        } else if (tokens[i][0] == '*') {
            num1 = pop(haha);
            num2 = pop(haha);
            push(haha, num2*num1);
        }
    }
    return pop(haha);
}

发表于 2024-09-30 00:50:59 回复(0)
C
ANLHXLA头像 ANLHXLA 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param tokens string字符串一维数组 
 * @param tokensLen int tokens数组长度
 * @return int整型
 */
int evalRPN(char** tokens, int tokensLen ) {
    // write code here
  int* s=(int*)malloc(sizeof(int) * tokensLen),index=-1;
  int val1,val2;
  for(int i=0;i<tokensLen;++i,++tokens){
    if(sscanf(*tokens,"%d",&val1))  s[++index]=val1;
    else{
      val2=s[index--];
      val1=s[index];
      switch(**tokens){
        case '*':s[index]=val1 * val2;break;
        case '/':s[index]=val1 / val2;break;
        case '+':s[index]=val1 + val2;break;
        case '-':s[index]=val1 - val2;break;
        default:break;
      }
    }
  }

  int result=s[index];
  free(s);
  return result;
}

发表于 2024-09-15 16:39:13 回复(0)
C
迷茫的小章鱼在开会头像 迷茫的小章鱼在开会
本人大三学生，代码有不足之处欢迎指正 
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
    char data;
    struct node* next;
};




void  NIBOLAN(char* p) {
    struct node* tail = malloc(sizeof(struct node));
    tail->next = NULL;
    struct node* pre = NULL;

    int i = 0;
    while (*(p + i) != '\0') 
    {
        if (*(p + i) >= 48 && *(p + i) <= 57) 
        {
            struct node* pnew = malloc(sizeof(struct node));
            pnew->data = *(p + i)-48;
            pnew->next = tail->next;
            tail->next = pnew;
            pre = tail->next->next;
        }

        else if (*(p + i) == '*' || *(p + i) == '/' || *(p + i) == '+' ||*(p + i) == '-') 
        {
            if (*(p + i + 1) == '*' || *(p + i + 1) == '/' || *(p + i + 1) == '+' ||*(p + i + 1) == '-') 
            {
                printf("error\n");
                break;
            } 
            else 
            {
                struct node *k=tail->next;
                if (*(p + i) == '*')
                {                
                  pre->data=(tail->next->data)*(pre->data);
                  tail->next=pre;
                  k->next=NULL;
                  free(k);            
                } 
                else if (*(p + i) == '/') 
                {               
                  pre->data=(tail->next->data)/(pre->data);
                  tail->next=pre;
                  k->next=NULL;
                  free(k);                         
                } 
                else if (*(p + i) == '-') 
                {
                  
                  pre->data=(tail->next->data)-(pre->data);
                  tail->next=pre;
                  k->next=NULL;
                  free(k);
                  
                 
                } 

                else if (*(p + i) == '+') 
                {
                  
                  pre->data=(tail->next->data)+(pre->data);
                  tail->next=pre;
                  k->next=NULL;
                  free(k);          
                } 
                else 
                {
                    printf("error\n");
                    break;//如果都不满足，在这就跳出了
                }
                
            }
        } 
        else {
            printf("error\n");
            break;
        }
        i++;
    }
    //整个循环执行完，打印出最终结果
    printf("%d",tail->next->data);
     


}


int main() {

    // char a[10];//只是给他分配了这么多的大小的空间，真实长度与用户输入有关

    // struct node *t=init();
    char a[10];
    scanf("%s", a);
    char* p = a;
    NIBOLAN(p);



}

编辑于 2024-04-10 22:09:46 回复(0)
C
慕林悠头像 慕林悠 
//先出栈的是右操作数，后出栈的是左操作数
typedef struct lnode {
    int data;
    struct lnode* next;
} node, *stack;

void Push(stack* p, int a) {
    stack cur = (stack)malloc(sizeof(node));
    if (cur == NULL) return;
    cur->data = a;
    cur->next = *p;
    *p = cur;
}
void Pop(stack* p) {
    if (*p != NULL) *p = (*p)->next;
}

int Add(int x, int y) {
    return x + y;
}
int Sub(int x, int y) {
    return x - y;
}
int Mul(int x, int y) {
    return x * y;
}
int Div(int x, int y) {
    return x / y;
}
int Signal(char* s) {
    if (strcmp(s, "+") == 0) return 1;
    else if (strcmp(s, "-") == 0) return 2;
    else if (strcmp(s, "*") == 0) return 3;
    else if (strcmp(s, "/") == 0) return 4;
    else return 0;
}

int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    int j = 0;
    stack s = NULL;
    int(*cal[5])(int, int) = {0, Add, Sub, Mul, Div};
    for (int i = 0; i < tokensLen; i++) {
        char* str =
            tokens[i];//在使用（*tokens）+i赋值变量时程序结果错误
        j = Signal(str);
        if (j) {//遇到运算符出栈运算并将结果入栈
            int right = s->data;
            Pop(&s);
            int left = s->data;
            Pop(&s);
            int z = (*cal[j])(left, right);//使用了函数指针数组
            Push(&s, z);
        } else {//非运算符，将字符串转换成整形入栈
            int m = atoi(str);
            Push(&s, m);
        }
    }
    return s->data;
}

发表于 2023-11-23 05:20:04 回复(0)
C
小鬼哥是大王头像 小鬼哥是大王
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param tokens string字符串一维数组
 * @param tokensLen int tokens数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    char *p;
    int num;
}data_t;

typedef struct stack {
    data_t data[10000];
    int top;
}stack_t;

data_t error = {NULL, -1};

stack_t *stack_create(void)
{
    stack_t *stack = (stack_t *)malloc(sizeof(stack_t));
    memset(stack, 0, sizeof(stack_t));
    stack->top = -1;
    return stack;
}

void stack_push(stack_t *stack, data_t data)
{
    stack->data[++stack->top] = data;
}

int is_empty(stack_t *stack)
{
    return stack->top == -1;
}

data_t stack_top(stack_t *stack)
{
    if(is_empty(stack))
        return error;
    return stack->data[stack->top];
}

data_t stack_pop(stack_t *stack)
{
    if(is_empty(stack)) {
        return error;
    }
    return stack->data[stack->top--];
}
int dataprocess(stack_t *stack, int sign)
{
        int a, b, result;
        data_t temp = {NULL, 0};
        temp = stack_pop(stack);
        if(temp.p)
            a = atoi(temp.p);
        else
            a = temp.num;       
        temp = stack_pop(stack);
        if(temp.p)
            b = atoi(temp.p);
        else
            b = temp.num;
        switch (sign) {
            case 0:
                result = b + a;
                break;
            case 1:
                result = b - a;
                break;
            case 2:
                result = b * a;
                break;
            case 3:
                result = b / a;
                break;
        }
        return result;
}

int evalRPN(char** tokens, int tokensLen ) {
    int i;
    stack_t *stack = stack_create();
    for(i = 0; i < tokensLen; i++) {
        data_t temp = {NULL, 0};
        if(!strcmp(tokens[i], "+")) {
 
            temp.num = dataprocess(stack, 0);
            stack_push(stack, temp);
            
        }else if(!strcmp(tokens[i], "-")) {
            temp.num = dataprocess(stack, 1);
            stack_push(stack, temp);
            
        }else if(!strcmp(tokens[i], "*")) {
            temp.num = dataprocess(stack, 2);
            stack_push(stack, temp);
            
        }else if(!strcmp(tokens[i], "/")) {
            temp.num = dataprocess(stack, 3);
            stack_push(stack, temp);
        }else {
            temp.p = tokens[i];
            stack_push(stack, temp);
        }
    }
    data_t result = stack_pop(stack);
    if(result.p)
        return atoi(result.p);
    else
        return result.num;
}
发表于 2022-04-17 15:11:08 回复(0)
提交观点

问题信息

数组 栈 基础数学
难度：
8条回答 8956浏览

热门推荐

通过挑战的用户

查看代码

相关试题

逆波兰表达式求值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号