資料結構正好學到堆疊,中綴,前綴,后綴運算式把人繞的不行,寫一個博客也算是總結一下這5個演算法:中綴運算式的計算,中綴運算式轉后綴運算式,后綴運算式計算,中綴運算式轉前綴運算式,前綴運算式計算
中綴運算式的計算
思路:
首先設立兩個堆疊,一個operator(運算子)堆疊,一個operand(運算元)堆疊,輸入數字進入operand堆疊,輸入運算子進入operator堆疊,運算式以’#‘開始和結束,
對于字符進堆疊,需要比較當前輸入的字符和operator堆疊頂字符的優先級大小:若當前運算子優先級高于堆疊頂運算子,則當前運算子進堆疊;若當前運算子優先級低于堆疊頂運算子,則堆疊頂運算子出堆疊,并且operand堆疊頂的兩個運算子也出堆疊,三者進行運算后的結果再次存入operand運算元堆疊,此時的當前運算子再繼續和堆疊頂運算子比較,直到優先級大于堆疊頂運算子為止,
當兩個’#'相遇時,也就是運算式結束是,讀取operand堆疊的堆疊頂元素的值,即為中綴運算式的值,
代碼共設12個函式:
(1)兩個堆疊的基本操作6個函式:Init(),Push(),Pop()
(2)判斷字符是否為數字的函式 In(char ch)
(3)獲取數字堆疊堆疊頂元素的函式GetTop1(Operand S)
(4)獲取運算子堆疊堆疊頂元素的函式GetTop2(Operator S)
(5)比較堆疊頂運算子和當前運算子優先級的函式Compare(Operator S,char ch)
(6)計算pop出的運算子和兩個運算元的函式Execute(int a,int b,char op)
(7)計算中綴運算式的值的函式 ExpEvaluation()
在這里我使用了一個二維陣列來存盤運算子的優先級,需要注意的是要搞清行和列哪一個是當前運算子,哪一個是堆疊頂運算子
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAXSIZE 100
char A[7] = {'+','-','*','/','(',')','#'};
char B[7][7] = {
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','!'},
{'>','>','>','>','!','>','>'},
{'<','<','<','<','<','!','='}
};
typedef struct
{
int* elem;
int top;
}Operand;//運算元堆疊
typedef struct
{
char* elem;
int top;
}Operator;//運算子堆疊
void Init_Operand(Operand* S)//初始化數字堆疊
{
S->elem = (int*)malloc(sizeof(int)*MAXSIZE);
S->top = -1;
if(S->elem == NULL)
{
printf("記憶體分配失敗!\n");
exit(-1);
}
else
printf("記憶體分配成功!\n");
}
void Push_Operand(Operand* S,int x)//數字x進堆疊
{
if(S->top == MAXSIZE-1)
{
printf("堆疊滿!\n");
exit(-1);
}
else
{
S->top++;
S->elem[S->top] = x;
printf("%d\n",S->elem[S->top]);
printf("入堆疊成功!\n");
}
}
void Pop_Operand(Operand* S,int *x)//數字出堆疊,將值存盤在x中
{
if(S->top<0)
{
printf("堆疊空!\n");
exit(-1);
}
else
{
*x = S->elem[S->top];
S->top--;
printf("%d\n",*x);
printf("出堆疊成功!\n");
}
}
void Init_Operator(Operator* S)//初始化運算子堆疊
{
S->elem = (char*)malloc(sizeof(char)*MAXSIZE);
S->top = -1;
if(S->elem == NULL)
{
printf("記憶體分配失敗!\n");
exit(-1);
}
else
printf("記憶體分配成功!\n");
}
void Push_Operator(Operator* S,char ch)//運算子ch進堆疊
{
if(S->top == MAXSIZE-1)
{
printf("堆疊滿!\n");
exit(-1);
}
else
{
S->top++;
S->elem[S->top] = ch;
printf("%c",S->elem[S->top]);
printf("進堆疊成功!\n");
}
}
void Pop_Operator(Operator* S,char* ch)//運算子ch出堆疊,將值儲存在ch中
{
if(S->top<0)
{
printf("堆疊空!\n");
exit(-1);
}
else
{
*ch = S->elem[S->top];
S->top--;
printf("%c",*ch);
printf("出堆疊成功!\n");
}
}
bool In(char ch)//判斷字符ch是否為數字,不是的話回傳true,是的話回傳false
{
for(int i=0;i<7;i++)
{
if(ch == A[i])
return true;
}
return false;
}
int GetTop1(Operand S)//獲取數字堆疊堆疊頂運算子的值
{
int x;
x = S.elem[S.top];
return x;
}
char GetTop2(Operator S)//獲取字符堆疊堆疊頂運算子的值
{
char ch;
ch = S.elem[S.top];
return ch;
}
char Compare(Operator S,char ch)//比較堆疊頂運算子和當前運算子的優先級
{
int temp1,temp2;
char c = GetTop2(S);//獲取堆疊頂運算子
for(int i=0;i<7;i++)
{
if(c==A[i])
temp1 = i;//獲取二維陣列的行坐標
if(ch==A[i])
temp2 = i;//獲取二維陣列的列坐標
}
return B[temp1][temp2];
}
int Execute(int a,int b,char op)//b是先彈出的,a是后彈出的
{
int v;
switch(op)
{
case '+':v = a+b;break;
case '-':v = a-b;break;
case '*':v = a*b;break;
case '/':v = a/b;break;
}
return v;
}
void ExpEvaluation()
{
int value;
char ch,op,x;
int a,b;
Operand s1;
Operator s2;
Init_Operand(&s1);//初始化數字堆疊
Init_Operator(&s2);//初始化字符堆疊
Push_Operator(&s2,'#');
ch = getchar();
while(ch!='#'||GetTop2(s2)!='#')
{
if(!In(ch))//不是執行運算子if
{
ch = ch - '0';
Push_Operand(&s1,ch);
fflush(stdin);//清慷訓沖區
ch = getchar();
}
else
{
switch(Compare(s2,ch))
{
case '<':
//堆疊頂運算子優先級低于當前運算子,入堆疊
{
Push_Operator(&s2,ch);
fflush(stdin);
ch = getchar();
}break;
case '>':
//堆疊頂運算子優先級高于當前運算子,出堆疊
{
Pop_Operator(&s2,&op);
Pop_Operand(&s1,&b);
Pop_Operand(&s1,&a);
value = Execute(a,b,op);
Push_Operand(&s1,value);
}break;
case '=':
{
Pop_Operator(&s2,&x);
fflush(stdin);
ch = getchar();
}break;
}
}
}
value = GetTop1(s1);
printf("中綴運算式的值為:%d",value);
}
int main()
{
ExpEvaluation();
return 0;
}
中綴運算式轉后綴運算式并計算
思路:
設立一個運算子堆疊operator和一個字符陣列,字符陣列用來存盤需要輸出的字符(包括數字和運算子),operator堆疊用來比較當前運算子和堆疊頂運算子的優先級大小,同樣運算式以‘#’開頭和結尾,
輸入若為數字直接存入字符陣列,若為運算子則壓入operator堆疊中,在入堆疊時,若當前運算子的優先級高于operator堆疊頂運算子,則當前運算子入堆疊;若當前運算子優先級低于operator堆疊頂運算子,則堆疊頂運算子出堆疊,進入字符陣列中,當前運算子再繼續與此時的堆疊頂運算子進行比較,直到當前運算子的優先級大于堆疊頂運算子為止,
對于括號,左括號‘(’直接入堆疊,當遇到右括號’)'時,不管優先級,開始將堆疊頂運算子按上面規律彈出,直到遇到左括號,將左括號彈出,然后讀取下一個字符,
后綴運算式的計算很簡單,只需要建立一個operand堆疊,當遇到數字則入堆疊,遇到字符,則彈出堆疊頂的兩個元素進行計算后將結果入堆疊,依次回圈,
代碼如下:
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAXSIZE 100
char A[7] = {'+','-','*','/','(',')','#'};
char B[7][7] = {
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','!'},
{'>','>','>','>','!','>','>'},
{'<','<','<','<','<','!','='}
};
typedef struct
{
char* elem;
int top;
}Operator;//存盤運算子的堆疊operator
typedef struct
{
char *elem;
int top;
}Array;//定義一個陣列的結構體型別,用來存盤字符
typedef struct
{
int* elem;
int top;
}Operand;//用來計算后綴運算式的值的數字堆疊
void Init_Operator(Operator* S)
{
S->elem = (char*)malloc(sizeof(char)*MAXSIZE);
S->top = -1;
if(S->elem == NULL)
{
printf("記憶體分配失敗!\n");
exit(-1);
}
else
printf("記憶體分配成功!\n");
}
void Push(Operator* S,char ch)
{
if(S->top == MAXSIZE-1)
{
printf("堆疊滿!\n");
exit(-1);
}
else
{
S->top++;
S->elem[S->top] = ch;
printf("%c\n",S->elem[S->top]);
printf("入堆疊成功!\n");
}
}
void Pop(Operator* S,char* ch)
{
if(S->top<0)
{
printf("堆疊空!\n");
exit(-1);
}
else
{
*ch = S->elem[S->top];
S->top--;
printf("%c\n",*ch);
printf("出堆疊成功!\n");
}
}
void Init_Array(Array* A)//初始化字符陣列
{
A->elem = (char*)malloc(sizeof(char)*MAXSIZE);
A->top = -1;
if(A->elem == NULL)
{
printf("記憶體分配失敗!\n");
exit(-1);
}
else
printf("記憶體分配成功!\n");
}
void Add(Array* A,char ch)//因為只需要向字符陣列中加入元素,故之定義add()
{
if(A->top==MAXSIZE)
{
printf("堆疊滿!\n");
exit(-1);
}
else
{
A->top++;
A->elem[A->top] = ch;
printf("%c ",A->elem[A->top]);
printf("入堆疊成功!\n");
}
}
void Init_Operand(Operand* S)//初始化數字堆疊
{
S->elem = (int*)malloc(sizeof(int)*MAXSIZE);
S->top = -1;
if(S->elem == NULL)
{
printf("記憶體分配失敗!\n");
exit(-1);
}
else
printf("記憶體分配成功!\n");
}
void Push_Operand(Operand* S,int x)
{
if(S->top==MAXSIZE-1)
{
printf("堆疊滿!\n");
exit(-1);
}
else
{
S->top++;
S->elem[S->top] = x;
printf("%d ",S->elem[S->top]);
printf("記憶體分配成功!\n");
}
}
void Pop_Operand(Operand* S,int *x)
{
if(S->top<0)
{
printf("堆疊空!\n");
exit(-1);
}
else
{
*x = S->elem[S->top];
S->top--;
printf("%d\n",*x);
printf("出堆疊成功!\n");
}
}
bool In(char ch)//是字符回傳true,是數字回傳false
{
for(int i=0;i<7;i++)
{
if(ch==A[i])
return true;
}
return false;
}
char GetTop(Operator S)
{
char ch;
ch = S.elem[S.top];
return ch;
}
int Execute(int a,int b,char op)
{
int v;
switch(op)
{
case '+':v = a+b;break;
case '-':v = a-b;break;
case '*':v = a*b;break;
case '/':v = a/b;break;
}
return v;
}
char Compare(char ch,Operator S)
{
int temp1,temp2;
char c;
c = GetTop(S);
for(int i=0;i<7;i++)
{
if(c==A[i])
temp1 = i;
if(ch==A[i])
temp2 = i;
}
return B[temp1][temp2];
}
void print(char ch)
{
if(In(ch))//是字符執行if陳述句
printf("%c ",ch);
else
printf("%d ",ch);
}
void print_Array(Array A)
{
for(int i=0;i<=A.top;i++)
{
printf("%c",A.elem[i]);
}
}
void Calcul_Exp(Array A)//后綴運算式的計算
{
int a,b,value;
//char temp;
Operand Stack;
Init_Operand(&Stack);
for(int i=0;i<=A.top;i++)
{
if(!In(A.elem[i]))//是數字,入堆疊
{
A.elem[i] = A.elem[i] - '0';
Push_Operand(&Stack,A.elem[i]);
}
else//字符,故 pop it
{
Pop_Operand(&Stack,&b);
Pop_Operand(&Stack,&a);
value = Execute(a,b,A.elem[i]);
Push_Operand(&Stack,value);
}
}
Pop_Operand(&Stack,&value);
printf("后綴運算式的值為:%d",value);
}
void Transfer()
{
char ch,op;
Operator Stack;
Array A;
Init_Array(&A);
Init_Operator(&Stack);
Push(&Stack,'#');
ch = getchar();
while(ch!='#')
{
if(!In(ch))//不是字符
{
Add(&A,ch);
fflush(stdin);
ch = getchar();
}
else//是字符
{
switch(Compare(ch,Stack))
{
case '<'://堆疊頂運算子優先級低于當前運算子
{
Push(&Stack,ch);
fflush(stdin);
ch = getchar();
}break;
case '>'://堆疊頂運算子的優先級高于當前運算子
{
if(GetTop(Stack)==')')
Pop(&Stack,&op);
else
{
Pop(&Stack,&op);
Add(&A,op);
}
}break;
case '=':
{
Pop(&Stack,&op);
fflush(stdin);
ch = getchar();
}break;
}
}
}
//printf("OK?\n");
while(GetTop(Stack)!='#')
{
Pop(&Stack,&op);
Add(&A,op);
}
print_Array(A);
Calcul_Exp(A);
}
int main()
{
Transfer();
//Calcul_Exp();
return 0;
}
中綴運算式轉前綴運算式
思路:
首先應建立兩個陣列結構體,一個用來存盤輸入的中綴運算式,一個用來存盤轉化后的前綴運算式;再應建立一個運算子operator堆疊,用來判定運算子的優先級大小,
首先輸入中綴運算式,將中綴運算式存放在一個字符陣列中,再從右至左讀取中綴運算式中的字符,若為數字則直接存放入前綴運算式陣列中;若為字符,則需判定該字符與operator堆疊堆疊頂字符的優先級:若該字符優先級高于堆疊頂運算子,則該字符入堆疊,若低于,則堆疊頂運算子出堆疊,該字符再與此時的堆疊頂運算子比較,直到其優先級高于堆疊頂運算子為止,
對于右括號‘)’,應壓入堆疊中;對于左括號‘(’,應依次將堆疊頂運算子彈出直到遇到右括號為止‘)’,值得注意的是,左括號和右括號都不需要進入前綴運算式陣列中,
注:為了簡便運算,我將運算子優先級表稍作調整
代碼如下:
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAXSIZE 100
char A[7] = {'+','-','*','/','(',')','#'};
char B[7][7] = {//此處對表做了一些修改
{'>','>','<','<','>','<','>'},
{'>','>','<','<','>','<','>'},
{'>','>','>','>','>','<','>'},
{'>','>','>','>','>','<','>'},
{'<','<','<','<','>','=','!'},
{'<','<','<','<','=','<','>'},
{'<','<','<','<','<','<','='}
};
typedef struct
{
char* elem;
int top;
}Operator;
typedef struct
{
char* elem;
int top;
}Array;
void Init_Operator(Operator* S)
{
S->elem = (char*)malloc(sizeof(char)*MAXSIZE);
S->top = -1;
if(S->elem == NULL)
{
printf("記憶體分配失敗!\n");
exit(-1);
}
else
printf("記憶體分配成功!\n");
}
void Push(Operator* S,char ch)
{
if(S->top == MAXSIZE-1)
{
printf("堆疊滿!\n");
exit(-1);
}
else
{
S->top++;
S->elem[S->top] = ch;
printf("%c\n",S->elem[S->top]);
printf("入堆疊成功!\n");
}
}
void Pop(Operator* S,char* ch)
{
if(S->top<0)
{
printf("堆疊空!\n");
exit(-1);
}
else
{
*ch = S->elem[S->top];
S->top--;
printf("%c\n",*ch);
printf("出堆疊成功!\n");
}
}
void Init_Array(Array* A)
{
A->elem = (char*)malloc(sizeof(char)*MAXSIZE);
A->top = -1;
if(A->elem==NULL)
{
printf("記憶體分配失敗!\n");
exit(-1);
}
else
printf("記憶體分配成功!\n");
}
void Add(Array* A,char ch)
{
printf("這里呢?\n");
if(A->top==MAXSIZE-1)
{
printf("堆疊滿!\n");
exit(-1);
}
else
{
A->top++;
A->elem[A->top] = ch;
printf("%c\n",A->elem[A->top]);
printf("插入成功!\n");
}
}
bool In(char ch)//是運算子回傳true,是數字回傳false
{
for(int i=0;i<7;i++)
{
if(ch==A[i])
return true;
}
return false;
}
char GetTop(Operator S)
{
char ch;
ch = S.elem[S.top];
//printf("%c\n",ch);
return ch;
}
char Compare(char ch,Operator S)
{
char c;
int temp1,temp2;
c = GetTop(S);
for(int i=0;i<7;i++)
{
if(c==A[i])
temp1 = i;
if(ch==A[i])
temp2 = i;
}
//printf("%c\n",B[temp1][temp2]);
return B[temp1][temp2];
}
void print(Array A)
{
for(int i=A.top;i>=0;i--)
{
printf("%c",A.elem[i]);
}
}
void Transfer()
{
char ch,op,temp;
Array A1,A2;
int i=0;
Operator Stack;
Init_Array(&A1);
Init_Array(&A2);
Init_Operator(&Stack);
Push(&Stack,'#');
printf("請輸入中綴運算式:\n");
ch = getchar();
while(ch!='#')
{
Add(&A1,ch);
fflush(stdin);
ch = getchar();
i = A1.top;
}
print(A1);
while(i>=0)
{
if(!In(A1.elem[i]))//是數字執行if陳述句
{
printf("第二步?\n");
temp = A1.elem[i];
Add(&A2,temp);
i--;
}
else
{
switch(Compare(A1.elem[i],Stack))
{
case '<'://堆疊頂運算子優先級低于當前運算子
{
Push(&Stack,A1.elem[i]);
i--;
}break;
case '>'://堆疊頂運算子優先級高于當前運算子
{
Pop(&Stack,&op);
Add(&A2,op);
}break;
case '=':
{
Pop(&Stack,&op);
i--;
}break;
}
}
}
while(GetTop(Stack)!='#')
{
Pop(&Stack,&op);
Add(&A2,op);
printf("%c\n",op);
}
print(A2);
}
int main()
{
Transfer();
return 0;
}
前綴運算式的計算
思路:
首先建立一個operand堆疊,由于將中綴運算式轉換為前綴后是將其存盤在一個字符陣列中的,則從左向右讀取該陣列中的元素,遇到數字進入operand堆疊,遇到運算子,則將堆疊頂的兩個元素依次彈出與該運算子進行計算,結果再入operand堆疊,當前綴運算式陣列掃描完成后,則operand堆疊頂的元素值即為前綴運算式的值,
代碼:
//將這些陳述句插入上面代碼即可運行
typedef struct
{
int* elem;
int top;
}Operand;
void Init_Operand(Operand* S)
{
S->elem = (int*)malloc(sizeof(int)*MAXSIZE);
S->top = -1;
if(S->elem == NULL)
{
printf("記憶體分配失敗!\n");
exit(-1);
}
else
printf("記憶體分配成功!\n");
}
void Push_Operand(Operand* S,int x)
{
if(S->top==MAXSIZE-1)
{
printf("堆疊滿!\n");
exit(-1);
}
else
{
S->top++;
S->elem[S->top] = x;
printf("%d ",S->elem[S->top]);
printf("記憶體分配成功!\n");
}
}
void Pop_Operand(Operand* S,int *x)
{
if(S->top<0)
{
printf("堆疊空!\n");
exit(-1);
}
else
{
*x = S->elem[S->top];
S->top--;
printf("%d\n",*x);
printf("出堆疊成功!\n");
}
}
int Execute(int a,int b,char op)
{
int v;
switch(op)
{
case '+':v = a+b;break;
case '-':v = a-b;break;
case '*':v = a*b;break;
case '/':v = a/b;break;
}
return v;
}
void Calcul_Exp(Array A)
{
int a,b,value;
Operand S;
Init_Operand(&S);
for(int i=0;i<=A.top;i++)
{
if(!In(A.elem[i]))//是數字執行if陳述句
{
A.elem[i] = A.elem[i] - '0';
//printf("%d\n",A.elem[i]);
//exit(-1);
Push_Operand(&S,A.elem[i]);
}
else
{
Pop_Operand(&S,&b);
Pop_Operand(&S,&a);
value = Execute(a,b,A.elem[i]);
Push_Operand(&S,value);
}
}
Pop_Operand(&S,&value);
printf("前綴運算式的值為:%d",value);
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/163916.html
標籤:其他
上一篇:mdk5軟體和stm32包的安裝以及stm32程式“LED閃爍”除錯,用Proteus仿真一個51程式設計和仿真
