给定一个逆波兰表达式,求表达式的值。
数据范围:表达式长度满足 ,表达式中仅包含数字和 + ,- , * , / ,其中数字的大小满足 。
#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); }
//先出栈的是右操作数,后出栈的是左操作数 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; }