数据结构算法C语言实现（八）--- 3.2栈的应用举例：迷宫求解与表达式求值

　　一.简介

　　迷宫求解：类似图的DFS。具体的算法思路可以参考书上的50、51页，不过书上只说了粗略的算法，实现起来还是有很多细节需要注意。大多数只是给了个抽象的名字，甚至参数类型，返回值也没说的很清楚，所以很多需要自己揣摩。这也体现了算法和程序设计语言的特点，算法更侧重本质的描述，而任何编程语言都要照顾到实现的细节以及数据类型等语法方面的需求。

　　表达式求值：

　　由于数据的读入是按照字符读入的，所以这个简单的小程序只能计算个位数的运算。

　　二.头文件

　　迷宫求解：

 //3_2_maze.h
 /**
 author:zhaoyu
 email:[e-mail]
 date:2016-6-8
 note:realize my textbook <<数据结构（C语言版）>>
 */
 //Page 51
 #ifndef _3_2_MAZE_H
 #define _3_2_MAZE_H
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include "head.h"
 #define STACK_INIT_SIZE 200//存储空间的初始分配值
 #define STACKINCREMENT 10//存储空间分配增量
 #define WALL -1
 #define PATH 1
 #define PASSED -2
 #define UNREACHABLE -3
 #define FINALPATH -4
 #define NMAX 50
 char Map[NMAX][NMAX];
 typedef struct{
     int x;
     int y;
 }PosType;
 typedef struct node_1{
     int x, y;
     struct node_1 *next;
 }MazeType;
 typedef struct{
     int ord;//通道块在路径上的序号
     PosType seat;//通道块在迷宫中的位置
     int direction;//从此通道块走向下一通道块的方向
 }SElemType;
 typedef struct{
     SElemType *base;//在栈构造之前和销毁之后，base 值为 NULL
     SElemType *top;//栈顶指针
     int stacksize;//当前已分配的存储空间，以元素为单位
 }SqStack;
 Status InitStack(SqStack &S)
 {
     //构造一个空栈 S
     S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
     if (!S.base)
     {
         exit(OVERFLOW);
     }
     S.top = S.base;
     S.stacksize = STACK_INIT_SIZE;
     return OK;
 }//InitStack
 void Assign_PosType(PosType &a, PosType b)
 {
     a.x = b.x;
     a.y = b.y;
 }//Assign_PosType
 Status Pass(PosType pos)
 {//可能写的不对，注意
     if (PATH == Map[pos.x][pos.y])
     {
         return TRUE;
     }
     else
     {
         return FALSE;
     }
 }//Pass
 void FoorPrint(PosType pos)
 {
     Map[pos.x][pos.y] = PASSED;
 }
 void Assign_SELemType(SElemType &e, int x, PosType pos, int y)
 {
     e.ord = x;
     Assign_PosType(e.seat, pos);
     e.direction = y;
 }
 Status Push(SqStack &S, SElemType e)
 {
     //插入元素 e 为新的栈顶元素
     if (S.top - S.base >= S.stacksize)
     {//栈满，追加存储空间
         S.base = (SElemType *)realloc(S.base,
             (S.stacksize+STACKINCREMENT)*sizeof(SElemType));
         if (!S.base)
         {
             exit(OVERFLOW);
         }
         S.top = S.base + S.stacksize;
         S.stacksize += STACKINCREMENT;
     }
     //*S.top++ = e;
     Assign_SELemType(*S.top++, e.ord, e.seat, e.direction);
     return OK;
 }//Push
 PosType NextPos(PosType pos, int direction)
 {
     PosType temp;
     switch (direction)
     {
         case :
         {
             temp.x = pos.x;
             temp.y = pos.y+;
             break;
         }
         case :
         {
             temp.x = pos.x + ;
             temp.y = pos.y;
             break;
         }
         case :
         {
             temp.x = pos.x;
             temp.y = pos.y - ;
             break;
         }
         case :
         {
             temp.x = pos.x - ;
             temp.y = pos.y;
             break;
         }
     }
     //加一个越界检查
     return temp;
 }
 Status StackEmpty(SqStack S)
 {
     //若 S 为空栈， 则返回 TRUE， 否则返回 FALSE
     if (S.base == S.top)
     {
         return TRUE;
     }
     else
     {
         return FALSE;
     }
 }
 Status Pop(SqStack &S, SElemType &e)
 {
     //若栈不空，则删除 S 的栈顶元素，用 e 返回其
     //值，并返回OK；否则返回ERROR
     if (S.top == S.base)
     {
         return ERROR;
     }
     //e = *--S.top;
     S.top--;
     Assign_SELemType(e, (*S.top).ord, (*S.top).seat, (*S.top).direction);
     return OK;
 }//Pop
 void FootPrint(PosType pos)
 {
     Map[pos.x][pos.y] = PASSED;
 }
 void MarkPrint(PosType pos)
 {
     Map[pos.x][pos.y] = UNREACHABLE;
 }
 void MakeMap(int size)
 {
     memset(Map, , sizeof(Map));
     char ch;
     getchar();
     for (int i = ; i <= size; i++)
     {
         for (int j = ; j <= size; j++)
         {
             scanf("%c", &ch);
             if ('X' == ch)
             {
                 Map[i][j] = UNREACHABLE;
             }
             else
             {
                 Map[i][j] = PATH;
             }
         }
         //attention '\n'
         getchar();
     }
     //Print maze
     for (int i = ; i <= size; i++)
     {
         for (int j = ; j <= size; j++)
         {
             if (UNREACHABLE == Map[i][j])
             {
                 printf("X");
             }
             else
             {
                 printf(" ");
             }
         }
         printf("\n");
     }
 }
 void PrintPath(SqStack S, int size)
 {
     SElemType e;
     SqStack temp;
     while (!StackEmpty(S))
     {
         Pop(S, e);
         Map[e.seat.x][e.seat.y] = FINALPATH;
     }
     for (int i = ; i <= size; i++)
     {
         for (int j = ; j <= size; j++)
         {
             if (UNREACHABLE == Map[i][j])
             {
                 printf("X");
             }
             else if (FINALPATH == Map[i][j])
             {
                 printf("O");
             }
             else
             {
                 printf(" ");
             }
         }
         printf("\n");
     }
 }
 Status MazePath(MazeType maze, PosType start, PosType end, int size)
 {
     //若迷宫 maze 中存在从入口 start 到出口 end 的通道，
     //则求得一条存放在栈中（从栈底到栈顶），并返回 TRUE，
     //否则返回 FALSE
     SqStack S;
     InitStack(S);
     //curpos = start
     PosType curpos;
     Assign_PosType(curpos, start);//设定当前位置为入口位置
     int curstep = ;//探索第一步
     SElemType e;
     do{
         if (TRUE == Pass(curpos))
         {//当前位置可以通过
             FootPrint(curpos);//留下足迹
             //e = (curstep, curpos, 1);
             Assign_SELemType(e, curstep, curpos, );
             Push(S, e);//加入路径
             if (curpos.x == end.x && curpos.y == end.y)
             {
                 //打印路径
                 printf("PATH EXIST\n");
                 PrintPath(S ,size);
                 return TRUE;
             }
             curpos = NextPos(curpos, );//下一位置是当前位置的东邻
             curstep++;//探索下一步
         }
         else
         {
             if (!StackEmpty(S))
             {
                 Pop(S, e);
                 while ( == e.direction && !StackEmpty(S))
                 {
                     MarkPrint(e.seat);
                     Pop(S, e);//留下不能通过的标记，并退回一步
                 }
                 if (e.direction < )
                 {
                     e.direction++;
                     Push(S, e);
                     curpos = NextPos(e.seat, e.direction);
                 }
             }
         }
     }while (!StackEmpty(S));

 }
 #endif

3_2_maze.h

　　表达式求值：

 //3_2_maze.h
 /**
 author:zhaoyu
 email:[e-mail]
 date:2016-6-8
 note:realize my textbook <<数据结构（C语言版）>>
 */
 //Page 53
 #ifndef _3_2_EXPRESSION_H_
 #define _3_2_EXPRESSION_H_
 #include "head.h"

 #define SElemType char
 #define OperandType float
 #define STACK_INIT_SIZE 100//存储空间的初始分配值
 #define STACKINCREMENT 10//存储空间分配增量
 typedef struct{
     SElemType *base;//在栈构造之前和销毁之后，base 值为 NULL
     SElemType *top;//栈顶指针
     int stacksize;//当前已分配的存储空间，以元素为单位
 }SqStack_Char;
 typedef struct{
     OperandType *base;//在栈构造之前和销毁之后，base 值为 NULL
     OperandType *top;//栈顶指针
     int stacksize;//当前已分配的存储空间，以元素为单位
 }SqStack_Float;
 Status InitStack_Char(SqStack_Char &S)
 {
     //构造一个空栈 S
     S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
     if (!S.base)
     {
         exit(OVERFLOW);
     }
     S.top = S.base;
     S.stacksize = STACK_INIT_SIZE;
     return OK;
 }//InitStack
 Status InitStack_Float(SqStack_Float &S)
 {
     //构造一个空栈 S
     S.base = (OperandType *)malloc(STACK_INIT_SIZE*sizeof(OperandType));
     if (!S.base)
     {
         exit(OVERFLOW);
     }
     S.top = S.base;
     S.stacksize = STACK_INIT_SIZE;
     return OK;
 }//InitStack
 Status Push_Char(SqStack_Char &S, SElemType e)
 {
     //插入元素 e 为新的栈顶元素
     if (S.top - S.base >= S.stacksize)
     {//栈满，追加存储空间
         S.base = (SElemType *)realloc(S.base,
             (S.stacksize+STACKINCREMENT)*sizeof(SElemType));
         if (!S.base)
         {
             exit(OVERFLOW);
         }
         S.top = S.base + S.stacksize;
         S.stacksize += STACKINCREMENT;
     }
     *S.top++ = e;
     return OK;
 }//Push
 SElemType GetTop_Char(SqStack_Char S)
 {
     //若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；
     //否则返回ERROR
     if (S.top == S.base)
     {
         return ERROR;
     }
     return *(S.top - );
 }//GetTop
 Status isInOPTR(SElemType c)
 {
     switch (c)
     {
         case '+':
         case '-':
         case '*':
         case '/':
         case '(':
         case ')':
         case '#':
         {
             return TRUE;
             break;
         }
         default:
         {
             return FALSE;
             break;
         }
     }
 }
 Status Push_Float(SqStack_Float &S, OperandType e)
 {
     //插入元素 e 为新的栈顶元素
     if (S.top - S.base >= S.stacksize)
     {//栈满，追加存储空间
         S.base = (OperandType *)realloc(S.base,
             (S.stacksize+STACKINCREMENT)*sizeof(OperandType));
         if (!S.base)
         {
             exit(OVERFLOW);
         }
         S.top = S.base + S.stacksize;
         S.stacksize += STACKINCREMENT;
     }
     *S.top++ = e;
     return OK;
 }//Push
 char Precede(SElemType a, SElemType b)
 {
     char R[][] =  {{'>','>','<','<','<','>','>'},
                     {'>','>','<','<','<','>','>'},
                     {'>','>','>','>','<','>','>'},
                     {'>','>','>','>','<','>','>'},
                     {'<','<','<','<','<','=','#'},
                     {'>','>','>','>','#','>','>'},
                     {'<','<','<','<','<','#','='}};
     int i,j;
     switch (a)
     {
         case '+':i=;break;
         case '-':i=;break;
         case '*':i=;break;
         case '/':i=;break;
         case '(':i=;break;
         case ')':i=;break;
         case '#':i=;break;
         default:i=;break;
     }
     switch (b)
     {
         case '+':j=;break;
         case '-':j=;break;
         case '*':j=;break;
         case '/':j=;break;
         case '(':j=;break;
         case ')':j=;break;
         case '#':j=;break;
         default:j=;break;
     }
     if ('#' == R[i][j])
     {
         printf("ERROR\n");
         exit(ERROR);
     }
     else
     {
         return R[i][j];
     }
 }
 Status Pop_Char(SqStack_Char &S, SElemType &e)
 {
     //若栈不空，则删除 S 的栈顶元素，用 e 返回其
     //值，并返回OK；否则返回ERROR
     if (S.top == S.base)
     {
         return ERROR;
     }
     e = *--S.top;
     return OK;
 }//Pop
 Status Pop_Float(SqStack_Float &S, OperandType &e)
 {
     //若栈不空，则删除 S 的栈顶元素，用 e 返回其
     //值，并返回OK；否则返回ERROR
     if (S.top == S.base)
     {
         return ERROR;
     }
     e = *--S.top;
     return OK;
 }//Pop
 OperandType Operate(OperandType a, SElemType theta, OperandType b)
 {
     switch (theta)
     {
         case '+': return a+b; break;
         case '-': return a-b; break;
         case '*': return a*b; break;
         case '/': return a/b; break;
         default:return ; break;
     }
 }
 OperandType GetTop_Float(SqStack_Float S)
 {
     //若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；
     //否则返回ERROR
     if (S.top == S.base)
     {
         return ERROR;
     }
     return *(S.top - );
 }//GetTop
 OperandType EvaluateExpression()
 {
     //算数表达式求值的算符优先算法。设 OPTR 和 OPND
     //分别为运算符栈和运算数栈，OP 为运算符集合
     SqStack_Char OPTR;
     SqStack_Float OPND;
     InitStack_Char(OPTR);
     Push_Char(OPTR, '#');
     InitStack_Float(OPND);
     char c = getchar(), x, theta;
     float a, b;
     while ('#' != c || GetTop_Char(OPTR) != '#')
     {
         //if (!In(c, OP))
         if (!isInOPTR(c))
         {
             float temp = c-'';
             Push_Float(OPND, temp);//不是运算符则进栈
             c = getchar();
         }
         else
         {
             switch (Precede(GetTop_Char(OPTR), c))
             {
                 case '<'://栈顶元素优先权低
                 {
                     Push_Char(OPTR, c);
                     c = getchar();
                     break;
                 }
                 case '='://脱括号并接收下一字符
                 {
                     Pop_Char(OPTR, x);
                     c = getchar();
                     break;
                 }
                 case '>'://退栈并将运算符结果入栈
                 {
                     Pop_Char(OPTR, theta);
                     Pop_Float(OPND, b);
                     Pop_Float(OPND, a);
                     Push_Float(OPND, Operate(a, theta, b));
                     break;
                 }
             }
         }
     }
     return GetTop_Float(OPND);
 }
 #endif

3_2_expression.h

　　三.CPP文件

　　迷宫求解：

 #include "3_2_maze.h"
 int main(int argc, char const *argv[])
 {
     freopen("map.txt", "r", stdin);
     printf("Map\n");
     int size;
     scanf("%d", &size);
     MakeMap(size);
     PosType start, end;
     scanf("%d%d", &start.x, &start.y);
     printf("start:\tx:%d\ty:%d\n", start.x, start.y);
     scanf("%d%d", &end.x, &end.y);
     printf("end:\tx:%d\ty:%d\n", end.x, end.y);
     MazeType maze;//un useded for me
     MazePath(maze, start, end, size);
     //PrintPath(size);
     return ;
 }

3_2_maze.cpp

　　表达式求值：

 #include "3_2_expression.h"
 int main(int argc, char const *argv[])
 {
     float ans;
     for (int i = ; i < ; ++i)
     {
         ans = EvaluateExpression();
         printf("%.3f\n", ans);
     }
     return ;
 }

3_2_expression.cpp

　　四.测试

　　迷宫求解：

　　

　　

　　表达式求值:

　　

　　五.迷宫求解的输入文件map.txt

XXXXXXXXXX
XOOXOOOXOX
XOOXOOOXOX
XOOOOXXOOX
XOXXXOOOOX
XOOOXOOOOX
XOXOOOXOOX
XOXXXOXXOX
XXOOOOOOOX
XXXXXXXXXX

map.txt

　　六.优化的表达式求值代码

　　用了一些简单的C++语法（主要是为了节省代码），写了一个可以计算较复杂表达式的程序。（STL不熟，估计以后看会很蹩脚！）

 #include <iostream>
 #include <string>
 #include <stack>
 #include <cstdio>
 #include <cstdlib>
 #include <map>
 using namespace std;
 bool isInOPTR(char ch){
     switch (ch)    {
         case '+':
         case '-':
         case '*':
         case '/':
         case '(':
         case ')':
         case '#':{
             return true;
             break;
         }
         default:{
             return false;
             break;
         }
     }
 }
 char Precede(char a, char b){
     map<char, int> myMap;
     myMap['+'] = ;
     myMap['-'] = ;
     myMap['*'] = ;
     myMap['/'] = ;
     myMap['('] = ;
     myMap[')'] = ;
     myMap['#'] = ;
     char R[][] =  {{'>','>','<','<','<','>','>'},
                     {'>','>','<','<','<','>','>'},
                     {'>','>','>','>','<','>','>'},
                     {'>','>','>','>','<','>','>'},
                     {'<','<','<','<','<','=','#'},
                     {'>','>','>','>','#','>','>'},
                     {'<','<','<','<','<','#','='}};
     if ('#' == R[myMap[a]][myMap[b]]){
         printf("Precede ERROE\n");
         printf("%c%c\n", a, b);
         exit(-);
     }
     return R[myMap[a]][myMap[b]];
 }
 float Caculate(float a, char theta, float b){
     switch (theta){
         case '+':{
             return a+b;
             break;
         }
         case '-':{
             return a-b;
             break;
         }
         case '*':{
             return a*b;
             break;
         }
         case '/':{
             return a/b;
         }
         default:{
             printf("Operator ERROR\n");
             exit(-);
         }
     }
 }
 void expression(void){
     string Str;
     getline(cin, Str);
     cout <<"Your input: " + Str + '\b' + ' ' << endl;
     char Operator = ' ';
     float Operand = ;
     stack<char> OPTR;
     stack<float> OPND;
     OPTR.push('#');
     int i = ;
     char number[];
     while (Operator != '#' || OPTR.top() != '#'){
         //fool code!!!
         for (int k = ;i <= Str.length();){
             if (isInOPTR(Str.at(i)))
             {
                 Operator = Str.at(i++);
                 break;
             }
             else
             {
                 number[k] = Str.at(i);
                 k++;
                 i++;
                 if (isInOPTR(Str.at(i)))
                 {
                     number[k] = '\0';
                     Operand = atof(number);
                     OPND.push(Operand);
                     continue;
                 }

             }
         }
         switch (Precede(OPTR.top(), Operator)){
             case '<':{
                 OPTR.push(Operator);
                 break;
             }
             case '=':{
                 OPTR.pop();
                 break;
             }
             case '>':{
                 float a, b;
                 char theta;
                 theta = OPTR.top();
                 OPTR.pop();
                 b = OPND.top();
                 OPND.pop();
                 a = OPND.top();
                 OPND.pop();
                 OPND.push(Caculate(a, theta, b));
                 i--;//attention!!!!!!!
                 break;
             }
         }
     }
     cout << "Answer: " <<OPND.top() << endl;

 }
 int main(int argc, char const *argv[])
 {
     freopen("in.txt", "r", stdin);
     freopen("out.txt", "w", stdout);
     for (int i = ; i < ; ++i)
     {
         expression();
     }
     return ;
 }

final_expression.cpp

　　测试数据：

3.2*-/+#
3.45*-(-)*#
*//#
2.22*(-)#
-#

in.txt

　　结果：

Your input: 3.2*-/+
Answer: 30.05
Your input: 3.45*-(-)*
Answer:
Your input: *//
Answer:
Your input: 2.22*(-)
Answer: -
Your input: -
Answer: 

out.txt