求表达式值时的栈内容图形表示
本文示范了扫描求解一个算术表达式时，操作数栈和运算符栈的情况。关于代码的主体，[bo]引用自《系统设计师教程》一书[/bo]，然后参考书中代码，略作修改，使用TC绘图模式来展示两个栈在扫描过程中的动态变化情况。
写的较快因此代码略显粗糙一些。
程序代码：/*运算表达式求值 ，我们用TC绘图形式表示操作数栈和运算符栈的情况！
*代码参考了《系统设计师教程》（王春森）一书中的代码。
*by hoodlum1980 2008年10月23日
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <graphics.h>
/*和绘制相关的定义*/
#define STACKWIDTH 100 /*栈宽度*/
#define CELLHEIGHT 20 /*栈网格高度*/
#define STACKLEFT_NUM 20 /**/
#define STACKLEFT_OP (STACKLEFT_NUM + STACKWIDTH + 20) /*栈左侧坐标*/
#define STACKBOTTOM 450 /*栈底部*/
#define TEXTBOXLEFT 20
#define TEXTBOXTOP 10
#define TEXTBOXWIDTH 500
#define TEXTBOXHEIGHT 24
#define INFOBOXLEFT (TEXTBOXLEFT) /*输出文本*/
#define INFOBOXTOP (TEXTBOXTOP + TEXTBOXHEIGHT + 10)
#define INFOBOXWIDTH (TEXTBOXWIDTH)
#define INFOBOXHEIGHT (TEXTBOXHEIGHT)
/*------------------------*/
#define POW 1 /* ^ */
#define MUL 2 /* * */
#define DIV 3 /* / */
#define ADD 4 /* + */
#define SUB 5 /* - */
#define Lp 6 /* ( */
#define Rp 7 /* ) */
#define END 8 /* \n */
#define Epsilon 1e-7
#define RADIX 10
typedef double NODE;
struct
{
char op; /*运算符字符*/
int code; /*该码映射到运算符，使运算符像操作数那样入栈和出栈*/
} opchTbl[]=
{
{'*',2}, {'/',3}, {'+',4}, {'-',5}, {'(',6}, {')',7}, {'^',1}, {'=',8},{' ',-1}
};
double num_stack[15]; /*操作数栈*/
char op_stack[15]; /*运算符栈*/
int numtop, optop; /*栈顶指针*/
int c = ' '; /*当前输入的字符*/
int TextPos=TEXTBOXLEFT+2;
/*运算符的栈外优先级: 【^ * / + - ( )】*/
char opchars[]=" ^*/+-()="; /*有运算符组成的字符串*/
int osp[]={5,3,3,2,2,5,1,1};
/*运算符的栈内优先级*/
int isp[]={4,3,3,2,2,0};
/*我们自己的GetChar函数*/
char GetChar()
{
char buffer[2];
buffer[1]=0;
buffer[0]=getch();
outtextxy(TextPos, TEXTBOXTOP+2, buffer);
TextPos+=12;
return buffer[0];
}
/*显示文本*/
void DisplayInfo(char *info)
{
bar(INFOBOXLEFT, INFOBOXTOP, INFOBOXLEFT+INFOBOXWIDTH, INFOBOXTOP+INFOBOXHEIGHT);
outtextxy(INFOBOXLEFT+2, INFOBOXTOP+INFOBOXHEIGHT/2, info);
}
/*绘制堆栈*/
void DrawStack(int stackleft)
{
int i;
setcolor(WHITE);
for(i=1;i<=15;i++)
{
bar(stackleft+1, STACKBOTTOM-i*CELLHEIGHT+1, stackleft+STACKWIDTH-1, STACKBOTTOM-(i-1)*CELLHEIGHT-1);
rectangle(stackleft, STACKBOTTOM-i*CELLHEIGHT, stackleft+STACKWIDTH, STACKBOTTOM-(i-1)*CELLHEIGHT);
}
}
void PushNum(double x)
{
char buffer[100];
sprintf(buffer,"%.3lf",x);
setcolor(WHITE);
outtextxy(STACKLEFT_NUM+5, STACKBOTTOM-numtop*CELLHEIGHT-CELLHEIGHT/2, buffer);
delay(6000);
num_stack[numtop++]=x;
}
void PushOp(char type)
{
char buffer[2];
buffer[0]=opchars[type];
buffer[1]=0;
setcolor(WHITE);
outtextxy(STACKLEFT_OP+10, STACKBOTTOM-optop*CELLHEIGHT-CELLHEIGHT/2, buffer);
delay(6000);
op_stack[optop++]=type;
}
double PopNum()
{
int i=numtop;
if(numtop<=0)
{
synError();
return 0;
}
bar(STACKLEFT_NUM+1, STACKBOTTOM-i*CELLHEIGHT+1, STACKLEFT_NUM+STACKWIDTH-2, STACKBOTTOM-(i-1)*CELLHEIGHT-1);
delay(6000);
return num_stack[--numtop];
}
char PopOp()
{
int i=optop;
if(optop<=0)
{
synError();
return 0;
}
bar(STACKLEFT_OP+1, STACKBOTTOM-i*CELLHEIGHT+1, STACKLEFT_OP+STACKWIDTH-2, STACKBOTTOM-(i-1)*CELLHEIGHT-1);
delay(6000);
return op_stack[--optop];
}
/*初始化！*/
void Init()
{
cleardevice();
setfillstyle(SOLID_FILL, BLACK);
DrawStack(STACKLEFT_OP);
DrawStack(STACKLEFT_NUM);
TextPos=TEXTBOXLEFT+2;
numtop=optop=0;
settextjustify(LEFT_TEXT, CENTER_TEXT);
}
/*表达式错误*/
int synError()
{
bar(500,20,600,40);
DisplayInfo("Input Error!");
GetChar();
closegraph();
exit(0);
}
/*计算操作*/
double eval(char tag, double left, double right)
{
int n;
double result;
switch(tag)
{
/*幂*/
case POW:
for(n=1, result=left; n<right; n++)
result*=left;
return result;
case ADD: return (left + right);
case SUB: return (left - right);
case MUL: return (left * right);
case DIV:
if(fabs(right)<=Epsilon)
{
DisplayInfo("divide by zero!");
exit(1);
}
return (left / right);
}
DisplayInfo("input error!");
return 1.0;
}
/*获取运算符，nump用于接收输入数字的指针，返回0表示接收到数字，返回其他值表示接收到运算符 */
int getToken(double *nump)
{
double dradix, num;
int i;
/*掠过空白字符*/
while(c==' ' || c=='\t') c=GetChar();
/*如果输入非数字字符*/
if(c<'0' || c>'9')
{
/*在运算符表中搜索该字符*/
for(i=0; opchTbl[i].code != -1 && opchTbl[i].op !=c; i++);
/*是否是非法字符？*/
if(opchTbl[i].code == -1) synError();
if(c != '=') c=GetChar(); /*c获取下一个字符*/
return opchTbl[i].code; /*返回运算符的内部码*/
}
num=0.0;
/*跟进输入数字*/
while(c >= '0' && c <= '9')
{
num = RADIX * num + ( c - '0' );
c = GetChar();
}
/*处理输入的小数点*/
if(c == '.')
{
dradix = 1.0/RADIX; /*小数单位*/
c=GetChar();
while(c >= '0' && c <= '9')
{
num = num + (c - '0')*dradix;
dradix/=RADIX;
c=GetChar(); /*跟进数字*/
}
}
*nump=num;
return 0; /*返回0表示接收到了一个操作数，返回其他值则代表运算符*/
}
/*-------------------------------*/
void main()
{
/*dop: 运算符， operand1：操作数1， operand2：操作数2， result：计算结果*/
double num, dop, operand1, operand2, result;
int type;
char ans, op, info[128]; /*ans接收用户回答是否继续时的按键*/
int gdriver=DETECT, gmode;
initgraph(&gdriver, &gmode, "");
do
{
Init();
DisplayInfo("Please Input: ");
PushOp(Lp); /* '(' 进栈*/
/*掠过前导空白字符*/
do {c=GetChar();} while(c==' ' || c=='\n' || c=='\t');
while(1)
{
type = getToken(&num); /*接收数字或运算符*/
if(type==0)
PushNum(num); /*数字进栈*/
else
{
/*处理运算符，比较栈外优先级和栈内优先级*/
if( osp[type-1] > isp[ op_stack[optop-1]-1 ] )
PushOp(type); /*栈外运算符进栈*/
else
{
while( osp[type-1] <= isp[ op_stack[optop-1]-1 ] && op_stack[optop-1] <=5)
{
op=PopOp(); /*出栈运算符！*/
operand2=PopNum(); /*出栈操作数*/
operand1=PopNum();
result=eval(op, operand1, operand2); /*双目运算*/
PushNum(result); /*运算结果入栈*/
}
if(type == END) break; /*一个表达式处理结束！*/
if(type == Rp) /*处理右括号')',将栈中的'('退去*/
{
do {dop=PopOp();} /*退栈至'(' */
while((char)dop != Lp);
}
else
PushOp(type); /*栈外运算符入栈*/
}
}
}
/*计算结果出栈*/
operand1=PopNum();
sprintf(info, "result = %lf continue ? (Y/N)", operand1);
DisplayInfo(info);
scanf("%c", &ans);
}
while(ans == 'y' || ans == 'Y');
}[[it] 本帖最后由 hoodlum1980 于 2008-10-23 03:40 编辑 [/it]]
calc_jfd.rar
(48.44 KB)
