栈的一个例子

august

求一表达式的值: 先将算术表达式转换成后缀表达式,然后对后缀表达式求值
     以字符形式输入,存放在字符型数组str中,后缀表达式存放在字符型数组exp中,将算术表达式转换成后缀表达式过程中用字符型数组stack作为栈.操作如下:
1.若ch 为数字,后后续所有数字依次存入数组exp,并以字符 #  标志数字结束
2.若ch为左括号 (   将特号插入栈 stack
3.若ch 为右括号 )  将栈stack中左括号 以前的字符依次删除并存入数组exp中,后将左括号 (  删除
4.若ch 为+,- ,将当前栈stack 中左括号以前的所有字符(运算符)依次删除并存入数组exp中,然后将ch
    插入栈stack中
5.若ch 为 *,  /  将当前栈stack中的栈顶端连续的 * , /   删除并依次存入数组exp中,然后ch插入栈stack   
   中,
6.若ch为 #  将栈stack的所有运算符依次删除并存入数组exp中,再将ch 存入数组exp中,最后在exp
    得出表达式后缀表示.

2. #include<stdio.h>
3. #define MAX 100
4. char exp[MAX];
5. void trans()            // 将算术表达式转换成后缀表达式
6. {
7.     char str[MAX];      // 存储原算术表达式
8.     char stack[MAX];    // 作栈使用
9.     char ch;                                                 [color=#FF0000]问题一:为什么下标以一为开始呢?[/color]    int sum,i,j,t,top=0;  // t 为 exp的下标，top 作stack的下标，i作str的下标
10.     printf("**********************8**************************************\n");
11.     printf("*输入一个求值的表达式，以#结束。只能包含+-*/运算符和正整数*\n");
12.     printf("**************************************************************\n");
13.     printf("算术表达式:");
14.     i=0;
15.     do                          // 获取用户输入的表达式
16.     {
17.         i++;
18.         scanf("%c",&str[i]);
19.     }while(str[i]!='#' && i!=MAX);
20.     sum=i;              // 记录输入表达式总的字符数
21.     t=1;i=1;
22.     ch=str[i];i++;
23.     while(ch!='#')
24.     {
25.         switch(ch)
26.         {
27.         case '(':             // 判定为左括号
28.             top++;stack[top]=ch;break;
29.         case ')':              // 判定为右括号
30.             while(stack[top]!='(')
31.             {
32.                 exp[t]=stack[top];top--;t++;
33.             }
34.             top--;
35.             break;          [color=#FF0000]问题二:这里开始,下面的top都是top++,为什么呢?[/color]
36.         case '+':                 // 判定为加减号
37.         case '-':
38.             while(top!=0 && stack[top]!='(')
39.             {
40.                 exp[t]=stack[top];top--;t++;
41.             }
42.             top++;stack[top]=ch;
43.             break;
44.         case '*':                // 判定为乘除号
45.         case '/':
46.             while(stack[top]=='*' || stack[top]=='/')
47.             {
48.                 exp[t]=stack[top];top--;t++;
49.             }
50.             top++;stack[top]=ch;
51.             break;
52.         case ' ':break;
53.         default:while(ch>='0' && ch<='9')    // 判定为数字
54.                 {
55.                     exp[t]=ch;t++;
56.                     ch=str[i];i++;
57.                 }
58.             i--;
59.             exp[t]='#';t++;
60.         }
61.         ch=str[i];i++;
62.     }
63.     while(top!=0)
64.     {
65.         exp[t]=stack[top];t++;top--;
66.     }
67.     exp[t]='#';
68.     printf("\n\t原来表达式:");
69.     for(j=1;j<sum;j++) printf("%c",str[j]);
70.     printf("\n\t后缀表达式:",exp);
71.     for(j=1;j<t;j++) printf("%c",exp[j]);
72. }
73. void compvalue()        // 计算后缀表达式的值
74. {
75.     float stack[MAX],d;   // 作为栈使用
76.     char ch;
77.     int t=1,top=0;       // t作为exp的下标，top作为stack的下标
78.   ch=exp[t];t++;
79.     while(ch!='#')          [color=#FF0000]问题三:这里是以数组exp所以经过数字就会有#为什么可以历遍整个表达式呢?[/color]    {
80.         switch(ch)
81.         {
82.         case '+':stack[top-1]=stack[top-1]+stack[top];
83.             top--;break;
84.         case '-':stack[top-1]=stack[top-1]-stack[top];
85.             top--;break;
86.         case '*':stack[top-1]=stack[top-1]*stack[top];
87.             top--;break;
88.         case '/':
89.             if(stack[top]!=0)
90.                 stack[top-1]=stack[top-1]/stack[top];
91.             else
92.             {
93.                 printf("\n\t除零错误!\n");
94.                 exit(0);
95.             }
96.             top--;break;
97.         default:d=0;
98.             while(ch>='0' && ch<='9')    // 判定为数字字符
99.             {
100. [color=#FF0000]  问题四:这里的d置0这样的表达式好像没啥意义吧?[/color]        
101.                                                                     d=10*d+ch-'0';           // 将数字字符转换成对应数值
102.                 ch=exp[t];t++;
103.             }
104.             top++;
105.             stack[top]=d;
106.         }
107.         ch=exp[t];t++;
108.     }
109.     printf("\n\t计算结果:%g\n",stack[top]);
110. }
111. void main()
112. {
113.     trans();
114.     compvalue();
115. }
117. 输入表达式(56-20)/(4+2)#
118. 原表达式:(56-20)/(4+2)
119. 后缀表达式:56#20#-4#2#+/
120. 结果:6

复制代码

总的来说对这例子整个运行过程都不太理解,请指点一下吧[s:6][s:6]

coolpay64

某沒仔細看，多見諒[s:78]
問題一：t不明。。。
問題二：top表示著stack 最後加入的index,每次++當然表代著最後
問題三： #是用作標記用，有點兒類似split中的標記，程式的協定問題
問題四：ch-'0' -> 因為ch是用ASCII格式記下，'0' 實際上不是int 的0，而是'0'這個字符的ASCII Code

august

问题一:它以 t 和top 作为下标,但开始时却以i=1 这样来赋值,就是将下标以一开始不是以0开始为什么 要   这样做?
问题三:while(ch!='#')  但表达式:56#20#-4#2#+/   56后就已经是#了,那不是到56就结束了吗?
问题四:ACII偶知道,但 d=10*d+ch-'0';有什么意义呢?d初始为0,这样的话还不与这样写 ,d=ch-'0'
PS:输入数字过程中比如56 在数组中是不是以5和6分开了存储呢?

Zelsazgh

Q1:个人选择问题....你也可以选择从0开始...只是思考起来总要想着下标-1不太舒服
Q3:default:while(ch>='0' && ch<='9')    // 判定为数字
                {
                    d=10*d+ch-'0';                    
                    exp[t]=ch;t++;
                    ch=str;i++;
                }
            i--;
            exp[t]='#';t++;
        }
这部份处理了数字分隔问题
Q4:有些编译器在没有给变量值的情况下会使用随机数...只是给个既定的值...一般不会有什么影响
QPS:看Q3的答就应当了解了公式d=d*10+ch-'0'是用于组合数字的...所以可以看出是按字符存储的...这种说法只是逆推导...一般来说字符串是由字符组成的...字符串就类似一个字符型数组...嗯..以上

shawind

好像在c中,char*和char[]是可以隐式转换的.

august

问题三:while(ch!='#')  但表达式:56#20#-4#2#+/  56后就已经是#了,那不是到56就结束了吗?
                    [s:5] 这问题好像还没答到点上吧?
还有这里:d=10*d+ch-'0';  跟 d=ch-'0'    没看出有什么不同.... [s:6]

coolpay64

d=10*d+ch-'0'
如果只運行一次，d=10*d+ch-'0' 和d=ch-'0'是沒分別
但如果ch 是字串的一部份
比如說str="123"; ch -> for loop中的運行變數
那d=10*d+ch-'0'會被運行3次
第一次，d的內容為 10*0+'1'-'0' = 1
第2次，d的內容為 10*1+'2'-'0' = 10+2=12
第3次，d的內容為 10*12+'3'-'0' = 120+3=123

LZ打入56也不會希望變成int時只餘下5或6吧

coolpay64

Q3
再看為何

2. while(ch!='#')
3. switch...{
4. .....
5.         default:d=0;
6.             while(ch>='0' && ch<='9')    // 判定为数字字符
7.             {
8.   问题四:这里的d置0这样的表达式好像没啥意义吧?      
9.                                                                     d=10*d+ch-'0';          // 将数字字符转换成对应数值
10.                 ch=exp[t];t++;
11.             }
12.             top++;
13.             stack[top]=d;
14.         }
15.         ch=exp[t];t++;
16. ....
17. }

复制代码

能走遍整個 后缀表达式:56#20#-4#2#+/

先指明

2.             stack[top]=d;
3.         }
4.         ch=exp[t];t++;

复制代码

是錯的。。正確代碼為

2.             stack[top]=d;
3.         ch=exp[t];t++;

复制代码

理所當然地，如果ch是'0'-＞'9'的話，程序會選行 default: 的路段
在while(ch>='0' && ch<='9')，就是指當ch依然是數字是，會不停運行這個loop
那何時會結束？就是ch不是'0'->'9'，那只可以是'#'
而這是的t剛好加了1(while loop 中最後一次運行ch=exp[t];t++;)
那嘛ch='#', exp[t]='0'->'9' or '+-*/'
再運行一次ch=exp[t];t++;
ch變成上面的exp[t] 也就是'0'->'9' or '+-*/'，所以程序能一直行下去