首页 > 代码库 > 逆波兰表达式
逆波兰表达式
一、 将中缀表达式转换成后缀表达式算法：
1、从左至右扫描 中缀表达式。
2、若读取的是操作数（数字），则判断该操作数的类型，并将该操作数存入操作数堆栈
3、若读取的是运算符
(1) 该运算符为左括号"("，则直接存入运算符堆栈。
(2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
(3) 该运算符为非括号运算符：
(a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
(b) 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
(c) 若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈。
4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。
二、逆波兰表达式求值算法：
1、循环扫描语法单元的项目。
2、如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
3、如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
4、如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。
5、将运算结果重新压入堆栈。
6、重复步骤2-5，全部运算完后，最后堆栈中数 即为结果值。
链接：逆波兰表达式求值
1 #include<stdio.h> 2 #include<stdlib.h> 3 typedef struct stu 4 { 5 char s; 6 struct stu *next; 7 }stack; 8 void push(stack **top,char c) 9 { 10 stack *p; 11 p=(stack *)malloc(sizeof(stack)); 12 p->s=c; 13 p->next=(*top); 14 *top=p; 15 } 16 void pop(stack **top) 17 { 18 *top=(*top)->next; 19 } 20 int yxj(char a,char b) 21 { 22 if((a==‘+‘||a==‘-‘)&&(b==‘*‘||b==‘\\‘)) 23 return 0; 24 return 1; 25 } 26 int main() 27 { 28 stack *top=NULL; 29 int m[110]; 30 char s[110],c[110]={0}; 31 int i,j=0,t=1; 32 gets(s); 33 for(i=0;s[i]!=‘@‘;i++){ 34 if(s[i]>=‘0‘&&s[i]<=‘9‘){ 35 c[j++]=s[i]; 36 t=0; 37 } 38 else{ 39 if(t==0){ 40 c[j++]=‘ ‘; 41 t=1; 42 } 43 if(top==NULL||s[i]==‘(‘||(s[i]!=‘)‘&&yxj(s[i],top->s))) 44 push(&top,s[i]); 45 else{ 46 if(s[i]==‘)‘){ 47 while(top->s!=‘(‘){ 48 c[j++]=top->s; 49 pop(&top); 50 } 51 pop(&top); 52 } 53 else{ 54 while(top!=NULL&&(!yxj(s[i],top->s))){ 55 c[j++]=top->s; 56 pop(&top); 57 } 58 push(&top,s[i]); 59 } 60 } 61 } 62 } 63 if(t==0) 64 c[j++]=‘ ‘; 65 while(top!=NULL){ 66 c[j++]=top->s; 67 pop(&top); 68 } 69 c[j]=0; 70 j=0; 71 for(i=0;c[i]!=‘\0‘;i++){ 72 if(c[i]>=‘0‘&&c[i]<=‘9‘){ 73 t=0; 74 for(;c[i]!=‘ ‘;i++) 75 t=t*10+c[i]-48; 76 m[j++]=t; 77 } 78 else{ 79 if(c[i]==‘+‘) 80 m[j-2]=m[j-2]+m[j-1]; 81 else if(c[i]==‘-‘) 82 m[j-2]=m[j-2]-m[j-1]; 83 else if(c[i]==‘*‘) 84 m[j-2]=m[j-2]*m[j-1]; 85 else if(c[i]==‘/‘) 86 m[j-2]=m[j-2]/m[j-1]; 87 j--; 88 } 89 } 90 printf("%d\n",m[0]); 91 return 0; 92 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。