复习栈
通过读取文件，实现一个迷宫，利用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 walked
push(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;
else
return -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 || comparePriority(getTopDate(),date) == 0)
{
profix[j]=getTopDate();
j++;
pop();
if(comparePriority(getTopDate(),date)==1||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;
}