栈的应用（表达式求值 迷宫路径）

一、表达式求值

算数表达式转化成后缀表达式

(56-20)/(2+4)转化成56#20#-4#2#+/

void trans(char* exp, char postexp[])
{
char e;
int i = 0;
SqStack* Optr;
InitStack(Optr);
while (*exp != '')
{
switch (*exp)
{
case'(':
Push(Optr, *exp);
exp++;
break;
case')':
Pop(Optr, e);
while (e != '(')
{
postexp[i] = e;
i++;
Pop(Optr, e);
}
exp++;
break;
case'+':
case'-':
while (!StackEmpty(Optr))
{
GetTop(Optr, e);
if (e != '(')
{
postexp[i] = e;
i++;
Pop(Optr, e);
}
else
break;
}
Push(Optr, *exp);
exp++;
break;
case'*':
case'/':
while (!StackEmpty(Optr))
{
GetTop(Optr, e);
if (e == '*' || e == '-')
{
postexp[i] = e;
i++;
Pop(Optr, e);
}
else
break;
}
Push(Optr, *exp);
exp++;
break;
default:
while (*exp >= '0' && *exp < '9')
{
postexp[i] = *exp;
i++;
exp++;
}
postexp[i] = '#';
i++;
}
}
while (!StackEmpty(Optr))
{
Pop(Optr, e);
postexp[i] = e;
i++;
}
postexp[i] = '';
DestroyStack(Optr);
}

　　后缀表达式求值

double CompValue(char *postexp)
{
SqStack1* Opond;
InitStack1(Opond);
double a=0, b=0, c=0, d=0, e=0;
while (*postexp != '')
{
switch (*postexp)
{
case'+':
Pop1(Opond, a);
Pop1(Opond, b);
c = b + a;
Push1(Opond, c);
break;
case'-':
Pop1(Opond, a);
Pop1(Opond, b);
c = b - a;
Push1(Opond, c);
break;
case'*':
Pop1(Opond, a);
Pop1(Opond, b);
c = b * a;
Push1(Opond, c);
break;
case'/':
Pop1(Opond, a);
Pop1(Opond, b);
if (a != 0)
{
c = b / a;
Push1(Opond, c);
break;
}
else
{
printf("除零错误n");
exit(0);
}
break;
default:
d = 0;
while (*postexp >= '0' && *postexp <= '9')
{
d= 10 * d+ *postexp - '0';
postexp++;
}
Push1(Opond, d);
break;
}
postexp++;
}
GetTop1(Opond, e);
DestroyStack1(Opond);
return e;
}

　　二、迷宫路径

typedef struct {
int i;
int j;
int di;
}Box;
typedef struct {
Box data[MAXSIZE];
int top ;
}SqStack;

　　

1	1	1	1	1	1	1	1	1	1
1	->		1				1		1
1			1				1		1
1					1	1			1
1		1	1	1					1
1									1
1		1				1			1
1		1	1	1		1	1		1
1	1							->	1
1	1	1	1	1	1	1	1	1	1

bool mgpath(int xi, int yi, int xe, int ye)
{
int i, j, di, i1, j1, k, t;
SqStack* st;
InitStack(st);
bool find = false;
Box e;
Box path[MAXSIZE];
e.i = xi;
e.j = yi;
e.di = -1;
mg[xi][yi] = -1;
Push(st, e);
while (!StackEmpty(st))
{
GetTop(st, e);
i = e.i;
j = e.j;
di = e.di;
if (i == xe && j == ye)
{
printf("一条迷宫路径如下：n");
k = 0; t = 0;
while (!StackEmpty(st))
{
Pop(st, e);
path[k] = e;
k++;
}
while (k >= 1)
{
k--;
printf("(%d,%d)t", path[k].i, path[k].j);
t++;
if (t % 5 == 0)
printf("n");
}
DestroyStack(st);
return true;
}
find = false;
while (di < 4)
{
di++;
switch (di)
{
case 0:
i1 = i - 1; j1 = j; break;
case 1:
i1 = i; j1 = j + 1; break;
case 2:
i1 = i + 1; j1 = j; break;
case 3:
i1 = i; j1 = j - 1; break;
}
if (mg[i1][j1] == 0)
{
find = true;
break;
}
}
if (find)
{
st->data[st->top].di = di;
e.i = i1;
e.j = j1;
e.di = -1;
Push(st, e);
mg[i1][j1] = -1;
}
else
{
Pop(st, e);
mg[e.i][e.j] = 0;
}
}
DestroyStack(st);
return false;
}