数据结构实验之栈与队列二：一般算术表达式转换成后缀式

Description

对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。

Input

输入一个算术表达式，以‘#’字符作为结束标志。

Output

输出该表达式转换所得到的后缀式。

Sample

Input

a*b+(c-d/e)*f#

Output

ab*cde/-f*+

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 char s[100005]; //分配栈的大小
 5 int main()
 6 {
 7     int top=0;
 8     char a;
 9     while(scanf("%c",&a))
10     {
11         if(a=='#')
12         break;
13         else if(a>='a'&&a<='z')
14             printf("%c",a); //字母直接输出
15         else if(a=='(')
16             s[++top]=a;  //左括号直接进栈
17         else if(a==')')
18         {
19             for(;s[top]!='(';top--)
20                 printf("%c",s[top]); //将括号中元素弹出栈
21             top--; //将'('弹出栈
22         }
23         else if(a=='+'||a=='-')
24         {
25             while(1)
26             {
27                 if(top==0||s[top]=='(')
28                 {
29                     s[++top]=a;
30                     break;
31                 }
32                 printf("%c",s[top--]); //若待压栈的操作符比栈顶操作符优先级高,则直接压栈,否则将栈顶元素出栈,再接着比较继续和栈顶元素的优先级.
33             }
34         }
35         else if(a=='*'||a=='/')
36         {
37             while(1)
38             {
39                 if(s[top]=='+'||s[top]=='-'||s[top]=='('||top==0)
40                 {
41                     s[++top]=a;
42                     break;
43                 }
44                 printf("%c",s[top--]); //若待压栈的操作符比栈顶操作符优先级高,则直接压栈,否则将栈顶元素出栈,再接着比较继续和栈顶元素的优先级.
45             }
46         }
47     }
48     for(;top>0;top--)
49             printf("%c",s[top]); //弹出栈中剩余元素
50     return 0;
51 }

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 char q[100005];
 6 int main()
 7 {
 8     int i,top,len;
 9     top=0;
10     char a[100005];
11     scanf("%s",a);
12     len=strlen(a);
13     for(i=0; i<len-1; i++)
14     {
15         if(a[i]>='a'&&a[i]<='z')
16             printf("%c",a[i]);
17         else
18         {
19             if(top==0||q[top-1]=='('||a[i]=='(')
20                 q[top++]=a[i];
21             else if(a[i]=='*'||a[i]=='/')
22             {
23                 while(1)
24                 {
25                     if(q[top-1]=='('||top==0||q[top-1]=='+'||q[top-1]=='-')
26                     {
27                         q[top++]=a[i];
28                         break;
29                     }
30                     printf("%c",q[--top]);
31                 }
32             }
33             else if(a[i]=='+'||a[i]=='-')
34             {
35                 while(1)
36                 {
37                     if(q[top-1]=='('||top==0)
38                     {
39                         q[top++]=a[i];
40                         break;
41                     }
42                     printf("%c",q[--top]);
43                 }
44             }
45             else if(a[i]==')')
46             {
47                 while(q[top-1]!='(')
48                 {
49                     printf("%c",q[--top]);
50                 }
51                 top--;
52             }
53         }
54     }
55     while(top!=0)
56     {
57         printf("%c",q[--top]);
58     }
59     return 0;
60 }