首页 > 代码库 > 逆波兰表达式的C实现
逆波兰表达式的C实现
复习下数据结构,用栈简单实现逆波兰表达式,参考文档:
http://www.nowamagic.net/librarys/veda/detail/2307http://www.nowamagic.net/librarys/veda/detail/2306
直接上代码:
/***code by lichmama from cnblogs.com*@逆波兰表达式的C实现*算术支持的运算模式:* 四则运算;* 操作数不得大于9;* 中间数(即运算当中的临时变量)不得超过127**/#include <stdio.h>#include <stdlib.h>typedef struct __STACK__ { char op; struct __STACK__ *next;}STACK, *PSTACK;void init(PSTACK *);void push(PSTACK *, char);void pop(PSTACK *, char *);void clear(PSTACK *);void destroy(PSTACK *);char getoplevel(char op){ if(op==‘+‘ || op==‘-‘) return 1; if(op==‘*‘ || op==‘/‘) return 2; return 0;}char calc(char *rpn){ char *p=rpn; char e; int x, y; PSTACK pStack; init(&pStack); while(*p){ if(0<=*p && *p<=9){ push(&pStack, *p); }else { pop(&pStack, &e);x=e; pop(&pStack, &e);y=e; switch(*p){ case ‘+‘:push(&pStack, y+x);break; case ‘-‘:push(&pStack, y-x);break; case ‘*‘:push(&pStack, y*x);break; case ‘/‘:push(&pStack, y/x);break; } } p++; } pop(&pStack, &e); free(pStack);pStack=NULL; return e;}int main(void){ char e; char old_exp[]="(3-1)*3+8/2+(9*3/(2+1)+3*4/6)-2="; char rpn_exp[256]=""; char *p=old_exp; char *r=rpn_exp; PSTACK gStack; init(&gStack);// while(*p!=‘\0‘ && *p!=‘=‘){ if(‘0‘<=*p && *p<=‘9‘){ *r++=(*p-‘0‘); }else if(*p==‘(‘){ push(&gStack, ‘(‘); }else if(*p==‘)‘){ for(;;){ pop(&gStack, &e); if(e==‘(‘)break; *r++=e; } }else if(*p==‘+‘ || *p==‘-‘ || *p==‘*‘ || *p==‘/‘){ if(getoplevel(gStack->op)<getoplevel(*p)){ push(&gStack, *p); }else{ for(;;){ pop(&gStack, &e); if(getoplevel(e)<getoplevel(*p)){ if(e!=‘#‘)push(&gStack, e); push(&gStack, *p);break; } *r++=e; } } } p++; } for(;;){ pop(&gStack, &e); if(e==‘#‘)break; *r++=e; } //printf("%s\n", rpn_exp); printf("%d\n", calc(rpn_exp));// clear(&gStack); destroy(&gStack); return 0;}void init(PSTACK *s){ *s=(PSTACK)malloc(sizeof(STACK)); (*s)->op=‘#‘; (*s)->next=NULL;}void push(PSTACK *s, char e){ PSTACK p=(PSTACK)malloc(sizeof(STACK)); p->op=e; p->next=*s; *s=p;}void pop(PSTACK *s, char *e){ if((*s)->next){ PSTACK p=(*s); *e=(*s)->op; *s=(*s)->next; free(p); p=NULL; }else *e=‘#‘;}void clear(PSTACK *s){ PSTACK p; while((*s)->next){ p=*s; *s=(*s)->next; free(p); p=NULL; }}void destroy(PSTACK *s){ free(*s); *s=NULL;}
注:改善操作数的限制可使用整形(或浮点型)数组存放中间变量。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。