复习栈

复习栈

复习栈

通过读取文件，实现一个迷宫，利用bfs，找出路径,

/***************************************************************Description: Inplement a maze and print the path with different symbols
Author: chendt
Version: 1.0
Date: 2021.3..23
History: So far,no changes.     ****************************************************************/
#include<iostream>
#include <fstream>
#include<iomanip>
using namespace std;
/*[Linked list---> Stack]  Use Linked lists to create a Stack,a struct is a nodes in Linked list.*/
typedef struct Stack_Element 
{int Maze_x,Maze_y;   /* X-coordinates,Y-coordinates */ struct Stack_Element * next;        
}* pointer; 
pointer ps=NULL; /* Top pointer of the Stack*/
int start_x,start_y,end_x,end_y; /*start and end coordinates of the maze*/
int row,column; /*the size of the maze*/
const int Maxsize=20; /*the Maxsize of the maze about row and column*/
int Maze[Maxsize][Maxsize]; /*use array to store the maze */
void Pop()        
{if(ps==NULL)cout<<"Stack empty,";else{pointer p;p = ps;ps=ps->next;free(p);  }}
void push(int x,int y)     
{pointer t=(pointer)malloc(sizeof(struct Stack_Element));t ->Maze_x=x;t->Maze_y=y;t->next=NULL;if(ps==NULL)ps=t;else{t->next=ps;ps=t;}
}
void readMaze() /*read data from txt file and print the digital maze */
{ifstream myfile("in.txt"); if (!myfile.is_open()){cout << "can not open this file" << endl;}else{myfile>>row;myfile>>column;myfile>>start_x;myfile>>start_y;myfile>>end_x;myfile>>end_y;for ( int i = 0; i <= row+1; i++){for(int j=0;j<=column+1;j++){if(i==0||i>=row+1||j==0||j>=column+1){Maze[i][j]=1;cout<<Maze[i][j]<<" ";}else{myfile>>Maze[i][j];cout<<Maze[i][j]<<" ";}}cout<<endl;}}myfile.close();
}
void printMaze(int row,int column) /*print the pattern of the maze*/
{	for(int i=0; i<row;i++){for(int j=0;j<column;j++){if(Maze[i][j]==1)cout<<"#"<<" "; /*symbol"#" marked as wall of the maze*/else if(Maze[i][j]==2)cout<<"*"<<" "; /*symbol"*" marked as position wallked*/else if(Maze[i][j]==3)cout<<"@"<<" "; /*symbol"@" marked as a dead end*/else if(Maze[i][j]==0)cout<<"  ";   /*the spaces" " marked as position walkable but untraveled*/}cout<<endl;}
}
/**************************************************************
Function: Mazepath
Description: use DFS algorithm to seach a path
Calls: printMaze()
**************************************************************/
void Mazepath()    
{int i=start_x,j=start_y;Maze[i][j]=2; //number 2 marked the position walkedpush(i,j);while (i!=end_x || j!=end_y){if(ps==NULL){cout<<"There is no one path from ( "<<start_x<<","<<start_y<<" ) "<<"to ( "<<end_x<<","<<end_y<<")."<<endl;break;}else{if(Maze[i][j+1]==0) /*judge whether it can be moved to the right*/{j++;Maze[i][j]=2; /*marked this position hass passed*/push(i,j);}else if(Maze[i+1][j]==0) /*judge whether it can be moved to the up*/{i++;Maze[i][j]=2;push(i,j);}else if(Maze[i][j-1]==0) /*judge whether it can be moved to the left*/{j--;Maze[i][j]=2;push(i,j);}else if(Maze[i-1][j]==0) /*judge whether it can be moved to the down*/{i--;Maze[i][j]=2;push(i,j);}else{Maze[i][j]=3;Pop();i=ps->Maze_x;j=ps->Maze_y;}}}printMaze(end_x+2,end_y+2);
}int main()                     
{readMaze();cout<<endl;Mazepath();return 0;
}

算中缀表达式的值

#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
const int Maxsize=40;
string expression;
char profix[Maxsize];
int j=0;
typedef struct StackOperator
{char Operator;struct StackOperator * next;
}*pointer;
pointer p=NULL;
void push(char data)
{pointer node=(pointer)malloc(sizeof(struct StackOperator));node->Operator=data;node->next=NULL;if(p==NULL)p=node;else{node->next=p;p=node;}
}
void pop()
{pointer d=p;p=p->next;free(d);
}char getTopDate()
{return p->Operator;
}int getPriority(char op)
{int prioritysize;if(op=='(')prioritysize=1;if(op=='+'||op=='-')prioritysize=2;if(op=='*'||op=='/')prioritysize=3;return prioritysize;
}
int comparePriority(char operator1,char operator2)
{int op1=getPriority(operator1);int op2=getPriority(operator2);if(op1>op2)return 1;else if(op1==op2)return 0;elsereturn -1;
}
void transform()
{cin>>expression;for(int i=0;i<expression.length();i++){char date=expression[i];char nextdate=expression[i+1];if(date>='0' && date<='9'){profix[j]=date;j++;if(nextdate=='+' || nextdate=='-' || nextdate=='*' ||nextdate=='/' ){profix[j]=' ';j++;}}else if(date == '('){push(date);}else if(date == ')'){while(getTopDate() != '('){profix[j]=getTopDate();j++;pop();}if(getTopDate()=='(')pop();}else{if(!p)push(date);else{if(comparePriority(getTopDate(),date)==-1) {push(date);}else{if(comparePriority(getTopDate(),date) == 1 ){profix[j]=getTopDate();j++;pop();if(p && comparePriority(getTopDate(),date) == 0){profix[j]=getTopDate();j++;pop();}push(date);continue;}if(comparePriority(getTopDate(),date) == 0){profix[j]=getTopDate();j++;pop();push(date);}}}}}while(p){profix[j]=p->Operator;j++;p=p->next;}}typedef struct StackOperant
{int Operant;struct StackOperant* next;}* pointer1;
pointer1 t=NULL;
void push2(int date)
{pointer1 node =(pointer1)malloc(sizeof(struct StackOperant));node->Operant=date;node->next=NULL;if(t==NULL)t=node;else{node->next=t;t=node;}
}
void pop2()
{pointer1 temp=t;t=t->next;free(temp);
}
int getOperant()
{return t->Operant;
}
int evaluation()
{int small,big,g,tm;for(int c=0;c<j;c++){char date=profix[c];if(date>='0' && date<='9'){int temp=(int)date-48;g=c+1;while(profix[g]!=' ' && profix[g]!='+' && profix[g]!='-' && profix[g]!='*' && profix[g]!='/'){temp=temp*10+(int)profix[g]-48;c++;g++;}push2(temp);}else{if(date==' ')continue;else{small=getOperant();pop2();big=getOperant();pop2();if(date == '+'){push2(big+small);}else if(date == '-'){push2(big-small);}else if(date == '*'){push2(big*small);}else{push2(big/small);}}}}return t->Operant;
}/*  switch(date){case '+':push2(big+small);case '-':push2(big-small);case '*':push2(big*small);case '/':push2(big/small);}*/int main()
{cout<<"Enter the expression: "<<endl;transform();cout<<"The Postfix is: ";for(int i=0; i<j; i++){char date=profix[i];cout<<date;}cout<<endl<<"Profix has trosformed!"<<endl;cout<<"the evalution of Profix is: ";cout<< evaluation()<<endl;}