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

雨点打透心脏的1/2处 2023-08-17 15:15 84阅读 0赞

一、表达式求值

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

(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 != '\0')
    		{
    			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] = '\0';
    		DestroyStack(Optr);
    }

后缀表达式求值

double CompValue(char *postexp)
    {
    	SqStack1* Opond;
    	InitStack1(Opond);
    	double a=0, b=0, c=0, d=0, e=0;
    	while (*postexp != '\0')
    	{
    		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;

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;
    }

转载于:https://www.cnblogs.com/KIROsola/p/11344651.html