#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1024
#define TRUE 1
#define FALSE 0
typedef char ElemType;
typedef struct { //順序堆疊定義
ElemType data[MAXSIZE];
int top; //堆疊頂指標
}SequenStack;
typedef struct {//佇列結構定義
ElemType data[MAXSIZE];
int front;
int rear;
}SequenQueue;
//初始化堆疊
SequenStack* InitStack( )
{
SequenStack *S = (SequenStack*)malloc(sizeof(SequenStack));
S->top = -1;
return S;
}
//判斷堆疊是否為空
int EmptyStack(SequenStack *S)
{
if(-1 == S->top)
return TRUE;
else
return FALSE;
}
//判斷堆疊是否滿
int FullStack(SequenStack *S)
{
if(S->top==MAXSIZE-1)
return true;
else
return FALSE;/****完善以下代碼****/
}
//進堆疊
int Push(SequenStack *S, ElemType e)
{
//判斷堆疊是否滿
if(FullStack(S))
{
printf("堆疊滿！");
return FALSE;
}
/****完善以下代碼******/
S->top++;//堆疊頂指標加1
S->data[S->top]=e;//存值到堆疊頂
return TRUE;
}
//出堆疊
int Pop(SequenStack *S, ElemType *e)
{
*e=S->data[S->top];/********完善以下代碼*******/
S->top--;
return true;
}
//取堆疊頂元素
ElemType GetTop(SequenStack *S)
{
return S->data[S->top];
}
//初始化佇列
SequenQueue* InitQueue()
{
SequenQueue* Q = NULL;
Q = (SequenQueue*)malloc(sizeof(SequenQueue));
Q->front = Q->rear = 0;
return Q;
}
//判斷佇列是否為空
int EmptyQueue(SequenQueue* Q)
{
if(Q->front == Q->rear)
return TRUE;
else
return FALSE;
}
//判斷佇列是否滿
int FullQueue(SequenQueue* Q)
{
if((Q->rear+1)%MAXSIZE==Q->front)/**完善代碼***/
return TRUE;
else
return FALSE;
}
//進隊
int EnQueue(SequenQueue* Q, ElemType e)
{
if(FullQueue(Q))
return FALSE;
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1)%MAXSIZE;
return TRUE;
}
//出隊
int DeQueue(SequenQueue* Q, ElemType *e)
{
*e=Q->data[Q->front];/***完善代碼****/
Q->front++;
return TRUE;
}
//取隊頭元素
ElemType GetHead(SequenQueue* Q)
{
return Q->data[Q->front];
}
//給運算子優先級排序
// 優先級順序：( < +, - < *, /
int getPriority(char op) {
int priority;
if (op == '*' || op == '/')
priority = 2;
if (op == '+' || op == '-')
priority = 1;
if (op == '(')
priority = 0;
return priority;
}
/*
* 輸出后綴運算式
*/
void PrintPostfix(SequenQueue *postfixQueue)
{
ElemType e;
while(!EmptyQueue(postfixQueue))
{
DeQueue(postfixQueue, &e);
printf("%c", e);
}
putchar('\n');
}
int Trans(char *expr, SequenQueue *postfixQueue)
{
char *p = expr;
ElemType e;
SequenStack *signStack = NULL; //符號堆疊,它是輔助堆疊
//初始化符號堆疊
signStack=InitStack( );/****完善代碼******/
//從左往右掃描運算式
while(*p != '\0')
{
if(*p >= '0' && *p <= '9') //數字直接入運算式佇列
{
EnQueue(postfixQueue, *p);
}
else if('(' == *p) //左括號，直接入符號堆疊
{
Push(signStack,*p);/***完善代碼*****/
}
else if(')' == *p) //如果是右括號，則將左括號前的所有符號出堆疊，并入運算式佇列
{
do{
Pop(signStack, &e); //符號出堆疊
if(e != '(') //將非(入運算式佇列
EnQueue(postfixQueue,e);/***完善代碼******/
}while((e != '(') && (!EmptyStack(signStack)));
}
else //其他符號，根據優先級選擇進堆疊
{
if(EmptyStack(signStack)) //如果符號堆疊為空，則直接將當前運算子入堆疊
{
Push(signStack, *p);
}
else
{
/*******完善代碼********/
while(getPriority(e)>getPriority(*p)) //比較當前運算子與堆疊頂的優先級
{
Pop(signStack, &e); //符號出堆疊
EnQueue(postfixQueue, e); //運算子入運算式佇列
if(EmptyStack(signStack)) //判斷符號堆疊是否為空
{
break;
}
}
//將當前運算子入堆疊
Push(signStack, *p);/*****完善代碼******/
}
}//end else
p++;
}//end while
//將符號堆疊全部入運算式佇列
while(!EmptyStack(signStack))
{
Pop(signStack, &e);
EnQueue(postfixQueue, e);
}
return TRUE;
}
int main(int argc, char *argv[])
{
SequenStack *S = InitStack(); //初始化堆疊
SequenQueue *Q = InitQueue(); //初始化堆疊
ElemType e; //元素e
Push(S,'A');
Push(S,'B');
Push(S,'C');
Push(S,'D');
Push(S,'E');
printf("%c",GetTop(S));
Pop(S,&e);
printf("%c",GetTop(S));
Pop(S,&e);
printf("%c",GetTop(S));
Pop(S,&e);
printf("%c",GetTop(S));
Pop(S,&e);
printf("%c",GetTop(S));
printf("\n");
EnQueue(Q,'A');
EnQueue(Q,'B');
EnQueue(Q,'C');
EnQueue(Q,'D');
EnQueue(Q,'E');
printf("%c",GetHead(Q));
DeQueue(Q,&e);
printf("%c",GetHead(Q));
DeQueue(Q,&e);
printf("%c",GetHead(Q));
DeQueue(Q,&e);
printf("%c",GetHead(Q));
DeQueue(Q,&e);
printf("%c",GetHead(Q));
printf("\n");
SequenQueue *postfixQueue = NULL; //運算式佇列
char expression[100];
//輸入計算運算式
gets(expression);
postfixQueue = InitQueue(); //初始化后綴運算式佇列
Trans(expression, postfixQueue);
PrintPostfix(postfixQueue);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/90263.html
標籤：新手樂園
上一篇：既然setbuf（stdout，NULL），是關閉標準輸出流緩沖區，輸出的字符沒有緩沖區，立即顯示，那么setbuf（stdin，NULL）是關閉標準輸入緩沖區