栈的一个例子
求一表达式的值: 先将算术表达式转换成后缀表达式,然后对后缀表达式求值以字符形式输入,存放在字符型数组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
得出表达式后缀表示.
#include<stdio.h>
#define MAX 100
char exp;
void trans() // 将算术表达式转换成后缀表达式
{
char str; // 存储原算术表达式
char stack; // 作栈使用
char ch; 问题一:为什么下标以一为开始呢? int sum,i,j,t,top=0;// t 为 exp的下标,top 作stack的下标,i作str的下标
printf("**********************8**************************************\n");
printf("*输入一个求值的表达式,以#结束。只能包含+-*/运算符和正整数*\n");
printf("**************************************************************\n");
printf("算术表达式:");
i=0;
do // 获取用户输入的表达式
{
i++;
scanf("%c",&str);
}while(str!='#' && i!=MAX);
sum=i; // 记录输入表达式总的字符数
t=1;i=1;
ch=str;i++;
while(ch!='#')
{
switch(ch)
{
case '(': // 判定为左括号
top++;stack=ch;break;
case ')': // 判定为右括号
while(stack!='(')
{
exp=stack;top--;t++;
}
top--;
break; 问题二:这里开始,下面的top都是top++,为什么呢?
case '+': // 判定为加减号
case '-':
while(top!=0 && stack!='(')
{
exp=stack;top--;t++;
}
top++;stack=ch;
break;
case '*': // 判定为乘除号
case '/':
while(stack=='*' || stack=='/')
{
exp=stack;top--;t++;
}
top++;stack=ch;
break;
case ' ':break;
default:while(ch>='0' && ch<='9') // 判定为数字
{
exp=ch;t++;
ch=str;i++;
}
i--;
exp='#';t++;
}
ch=str;i++;
}
while(top!=0)
{
exp=stack;t++;top--;
}
exp='#';
printf("\n\t原来表达式:");
for(j=1;j<sum;j++) printf("%c",str);
printf("\n\t后缀表达式:",exp);
for(j=1;j<t;j++) printf("%c",exp);
}
void compvalue() // 计算后缀表达式的值
{
float stack,d; // 作为栈使用
char ch;
int t=1,top=0; // t作为exp的下标,top作为stack的下标
ch=exp;t++;
while(ch!='#') 问题三:这里是以数组exp所以经过数字就会有#为什么可以历遍整个表达式呢? {
switch(ch)
{
case '+':stack=stack+stack;
top--;break;
case '-':stack=stack-stack;
top--;break;
case '*':stack=stack*stack;
top--;break;
case '/':
if(stack!=0)
stack=stack/stack;
else
{
printf("\n\t除零错误!\n");
exit(0);
}
top--;break;
default:d=0;
while(ch>='0' && ch<='9') // 判定为数字字符
{
问题四:这里的d置0这样的表达式好像没啥意义吧?
d=10*d+ch-'0'; // 将数字字符转换成对应数值
ch=exp;t++;
}
top++;
stack=d;
}
ch=exp;t++;
}
printf("\n\t计算结果:%g\n",stack);
}
void main()
{
trans();
compvalue();
}
输入表达式(56-20)/(4+2)#
原表达式:(56-20)/(4+2)
后缀表达式:56#20#-4#2#+/
结果:6
总的来说对这例子整个运行过程都不太理解,请指点一下吧 某沒仔細看,多見諒
問題一:t不明。。。
問題二:top表示著stack 最後加入的index,每次++當然表代著最後
問題三: #是用作標記用,有點兒類似split中的標記,程式的協定問題
問題四:ch-'0' -> 因為ch是用ASCII格式記下,'0' 實際上不是int 的0,而是'0'這個字符的ASCII Code 问题一:它以 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分开了存储呢? Q1:个人选择问题....你也可以选择从0开始...只是思考起来总要想着下标-1不太舒服
Q3:default:while(ch>='0' && ch<='9') // 判定为数字
{
d=10*d+ch-'0';
exp=ch;t++;
ch=str;i++;
}
i--;
exp='#';t++;
}
这部份处理了数字分隔问题
Q4:有些编译器在没有给变量值的情况下会使用随机数...只是给个既定的值...一般不会有什么影响
QPS:看Q3的答就应当了解了公式d=d*10+ch-'0'是用于组合数字的...所以可以看出是按字符存储的...这种说法只是逆推导...一般来说字符串是由字符组成的...字符串就类似一个字符型数组...嗯..以上 好像在c中,char*和char[]是可以隐式转换的. 问题三:while(ch!='#')但表达式:56#20#-4#2#+/56后就已经是#了,那不是到56就结束了吗?
这问题好像还没答到点上吧?
还有这里:d=10*d+ch-'0';跟 d=ch-'0' 没看出有什么不同.... 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吧 Q3
再看為何
while(ch!='#')
switch...{
.....
default:d=0;
while(ch>='0' && ch<='9') // 判定为数字字符
{
问题四:这里的d置0这样的表达式好像没啥意义吧?
d=10*d+ch-'0'; // 将数字字符转换成对应数值
ch=exp;t++;
}
top++;
stack=d;
}
ch=exp;t++;
....
}
能走遍整個 后缀表达式:56#20#-4#2#+/
先指明
stack=d;
}
ch=exp;t++;
是錯的。。正確代碼為
stack=d;
ch=exp;t++;
理所當然地,如果ch是'0'->'9'的話,程序會選行 default: 的路段
在while(ch>='0' && ch<='9'),就是指當ch依然是數字是,會不停運行這個loop
那何時會結束?就是ch不是'0'->'9',那只可以是'#'
而這是的t剛好加了1(while loop 中最後一次運行ch=exp;t++;)
那嘛ch='#', exp='0'->'9' or '+-*/'
再運行一次ch=exp;t++;
ch變成上面的exp 也就是'0'->'9' or '+-*/',所以程序能一直行下去
页:
[1]