3、.h>
#include
#include
#include
函數(shù)說明如下
SeqStack1; /*定義一個(gè)堆棧SeqStack1*/
void StackInitiate1(SeqStack1 *S) /*初始化堆棧1，棧底為‘#’*/
void StackPush1(SeqStack1 *S,DataType x) /*將元素壓入堆棧1*/
void StackPop1(SeqStack1 *S,DataType *x
4、) /*彈出堆棧1的棧頂元素*/
int StackTop1(SeqStack1 S,DataType *d) /*取堆棧1的棧頂元素*/
SeqStack2; /*定義一個(gè)順序堆棧SeqStack2*/
void StackInitiate2(SeqStack2 *S) /*初始化堆棧2*/
BiTreeNode * StackPop2(SeqStack2 *S) /*從堆棧2中彈出棧頂元素*/
BiTreeNode; /*定義二叉樹的結(jié)點(diǎn)*/
推
5、薦精選
void Initiate(BiTreeNode **root) /*初始化樹的根結(jié)點(diǎn)*/
void print(BiTreeNode *bt,int n) /*逆時(shí)針打印二叉樹*/
void StackPush2(SeqStack2 *S,BiTreeNode *x) /*將二叉樹結(jié)點(diǎn)壓入堆棧2*/
int Convert(char a[500],char b[500][100],SeqStack1 *S,int n) /*將待求表達(dá)式轉(zhuǎn)換為后綴形式*/
BiTreeNode * BuildTree(char b[500][1
6、00],int n)/*根據(jù)表達(dá)式的后綴形式，構(gòu)造相應(yīng)的二叉樹*/
LSNode; /*定義了鏈?zhǔn)蕉褩Ｓ糜谙旅鏅z測(cè)表達(dá)式的括號(hào)匹配*/
void StackInitiate(LSNode** head) /*初始化堆棧*/
int StackNotEmpty(LSNode* head) /*檢測(cè)堆棧是否為空的函數(shù)*/
int StackPush(LSNode* head,DataType x) /*將元素入棧*/
int StackPop(LSNode* head,DataType* d) /*彈出棧頂元素*/
int Stac
7、kTop(LSNode* head,DataType *d) /*取棧頂元素*/
void Destroy(LSNode* head) /*撤消*/
void ExplsCorrect(char exp[]) /*檢測(cè)輸入表達(dá)式的括號(hào)匹配函數(shù)*/
i
3. 詳細(xì)設(shè)計(jì)
void StackInitiate(LSNode** head)
{
if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1);
(*head)->next=NULL;
} /*初始化堆棧*/
int St
8、ackNotEmpty(LSNode* head)
{
if(head->next==NULL)return 0;
else return 1;
}
/*檢測(cè)堆棧是否為空的函數(shù)，若為空，返回0，否則返回1*/
typedef struct snode
{
DataType data;
struct snode* next;
}LSNode;
/*定義了鏈表的結(jié)點(diǎn)用于下面檢測(cè)表達(dá)式的括號(hào)匹配*/
int StackPop(LSNode* head,DataType* d)
{
LSNode* p=head->next;
if(p==NULL)
9、
{
推薦精選
cout<<"堆棧已空出錯(cuò)"<next=p->next;
*d=p->data;
free(p);
return 1;
}
/*彈出棧頂元素*/
int StackPush(LSNode* head,DataType x)
{
LSNode* p;
if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL)
{
cout<<"內(nèi)存空間不足無法插入!"<d
10、ata=x;
p->next=head->next;
head->next=p;
return 1;
}
/*將元素入棧*/
int StackTop(LSNode* head,DataType *d)
{
LSNode* p=head->next;
if(p==NULL)
{
cout<<"堆棧已空出錯(cuò)"<data;
return 1;
}
/*取棧頂元素*/
void Destroy(LSNode* head)
推薦精選
{
LSNode* p,*p1;
11、
p=head;
while(p!=NULL)
{
p1=p;
p=p->next;
free(p1);
}
}/*撤消*/
三．調(diào)試分析
在運(yùn)行程序的過程中，碰到了一些錯(cuò)誤，其中有很多是括號(hào)和分號(hào)的問題，看來以后寫程序要更加細(xì)心才行。
四．用戶手冊(cè)
此程序中'&''|''~'分別代表代表'與' '或' '非'運(yùn)算
首先輸入一個(gè)包含變量，運(yùn)算符表達(dá)式，再按Enter執(zhí)行。再依次輸入各變量的值。如果不繼續(xù)輸入，按0退出。再按y繼續(xù)或者n退出。
五．測(cè)試數(shù)據(jù)及測(cè)試結(jié)果
輸入a&b&c
推薦精選
六． 源程
12、序清單
typedef struct
{
DataType stack[1000];
int top;
}SeqStack1;
//用來實(shí)現(xiàn)將輸入的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
void StackInitiate1(SeqStack1 *S) //初始化，棧底為#
推薦精選
{
S->stack[0]='#';
S->top = 1;
}
void StackPush1(SeqStack1 *S,DataType x) //將元素壓入堆棧1
{
13、
S->stack[S->top] = x ;
S->top++;
}
void StackPop1(SeqStack1 *S,DataType *x) //彈出堆棧1的棧頂元素
{
S->top--;
*x = S->stack[S->top];
}
int StackTop1(SeqStack1 S,DataType *d) //取堆棧1的棧頂元素
{
if(S.top<=0)
{
cout<<"堆棧已空!\n"<
14、
15、[500],char b[500][100],SeqStack1 *S,int n)//將待求表達(dá)式子轉(zhuǎn)換為后綴形式
{
int i,j,k=0;
char character;
for(i=0;i
16、cter=='#'&&a[i]!='#')||(character=='|'&&a[i]=='~')||(character=='|'&&a[i]=='&')
||(character=='|'&&a[i]=='(')||(character=='&'&&a[i]=='~')||(character=='&'&&a[i]=='(')
||(character=='~'&&a[i]=='(')||(character=='('&&a[i]!=')'))
{
StackPush1(S,a[i]); //當(dāng)中綴表達(dá)式當(dāng)前運(yùn)算符優(yōu)先級(jí)較高時(shí)，進(jìn)棧
17、 break;
}
else if(character=='('&&a[i]==')') //'('和')'相遇時(shí)，將'('退棧，接著讀下面的
{
StackPop1(S,&character);
break;
}
else
{
StackPop1(S,&character); //當(dāng)棧頂元素優(yōu)先級(jí)較高時(shí)，退棧
b[k][0]=character;
b[k][1]=0;
k++;
18、
continue;
}
}
推薦精選
continue;
}
if(!IsOptr(a[i]))
{
j=0;
while(!IsOptr(a[i]))
{
b[k][j]=a[i]; //當(dāng)前為變量時(shí)，直接存入二維數(shù)組b中
j++;
i++;
}
i--;
b[k][j]=0; //表示該行結(jié)束
k++;
}
}
return 0;
19、
}
#include
typedef struct Node
{
DataType data[1000];
struct Node *leftChild;
struct Node *rightChild;
struct Node *parent;
}BiTreeNode;//定義二叉樹的結(jié)點(diǎn)
typedef struct
{
BiTreeNode * address[1000]; //定義成樹結(jié)點(diǎn)的指針，方便下面構(gòu)造二叉樹時(shí)，對(duì)結(jié)點(diǎn)的保存
int
20、top;
}SeqStack2;
void Initiate(BiTreeNode **root) //初始化樹的根結(jié)點(diǎn)
{
*root = (BiTreeNode * ) malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
推薦精選
(*root)->parent=NULL;
}
void print(BiTreeNode *bt,int n) //逆時(shí)針
21、打印二叉樹
{
int i,j,m;
if(bt==NULL) return;
print(bt->rightChild,n+1);
for(i=0;i=0)
{
cout<<"---";
m=strlen(bt->data);
for(j=0;jdata[j];
cout<leftChild,n+1);
}
////////////
22、/////////////////////////////////////////////////////////////////////////////////////////////
void StackInitiate2(SeqStack2 *S) //初始化堆棧2
{
S->top = 0;
}
void StackPush2(SeqStack2 *S,BiTreeNode *x) //將二叉樹結(jié)點(diǎn)壓入堆棧2
{
S->address[S->top] = x;
S->
23、top++;
}
BiTreeNode * StackPop2(SeqStack2 *S) //從堆棧2中彈出棧頂元素
{
BiTreeNode *x;
S->top--;
x = S->address[S->top];
return x;
}
推薦精選
BiTreeNode * BuildTree(char b[500][100],int n)
{
int i;
BiTreeNode *p,*q,*o;
SeqStack2 s;
StackInitiate2(&s);
24、
for(i=0;idata,b[i]); //將變量賦給結(jié)點(diǎn)P的數(shù)據(jù)域
p->rightChild=NULL; //初始化左右子樹以及雙親指針
p->leftChild=NULL;
p->parent=NULL;
if(b[i][0]=='~')
{
q=StackPop2(&s);
p->
25、rightChild=q; //將彈出后的結(jié)點(diǎn)作為右孩子
q->parent=p;
StackPush2(&s,p);
}
else if(b[i][0]=='|' || b[i][0]=='&')
{
q=StackPop2(&s); //彈出q作為右孩子
o=StackPop2(&s); //彈出0作為左孩子
q->parent=p;
o->paren
26、t=p;
p->leftChild=o;
p->rightChild=q;
StackPush2(&s,p); //根結(jié)點(diǎn)入棧
}
else
{
StackPush2(&s,p);
}
}
p=StackPop2(&s); //彈出構(gòu)造好的二叉數(shù)的根結(jié)點(diǎn)指針，并返回
return p;
}
int PostOrder(BiTreeNode *t,int c[500],cha
27、r b[500][100],int n) //后序遍歷該樹
{
推薦精選
int n1,n2,i;
if(t!=NULL)
{
n1=PostOrder(t->leftChild,c,b,n);
n2=PostOrder(t->rightChild,c,b,n);
if(t->data[0]=='~') //遇到'~'將值置反
{
if(n2==0) return 1;
if(n2==1) return 0;
}
els
28、e if(t->data[0]=='&') //遇到'&'只有兩個(gè)都為真時(shí)才為真
{
if(n1==1 && n2==1) return 1;
else return 0;
}
else if(t->data[0]=='|') //遇到'|'只有兩個(gè)都為假時(shí)才為假
{
if(n1==0 && n2==0) return 0;
else return 1;
}
else
{
for(i=0;i
29、{
if(!(strcmp( b[i],t->data))) break; //當(dāng)該結(jié)點(diǎn)數(shù)據(jù)域?yàn)樽兞繒r(shí)
}
return c[i]; //直接返回該變量的真值
}
}
return -1;
}
ypedef struct snode
{
DataType data;
struct snode* next;
}LSNode; //定義鏈?zhǔn)蕉褩５慕Y(jié)點(diǎn)，用于下面檢測(cè)表達(dá)式的括號(hào)匹配
void StackInitiate(LSNode** head
30、)
{
推薦精選
if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1);
(*head)->next=NULL;
}//初始化堆棧
int StackNotEmpty(LSNode* head)
{
if(head->next==NULL)return 0;
else return 1;
}//檢測(cè)堆棧是否為空的函數(shù)，若為空，返回0，否則返回1
int StackPush(LSNode* head,DataType x)
{
LSNode* p;
if((p=(LSNode*)mal
31、loc(sizeof(LSNode)))==NULL)
{
cout<<"內(nèi)存空間不足無法插入!"<data=x;
p->next=head->next;
head->next=p;
return 1;
}//將元素入棧
int StackPop(LSNode* head,DataType* d)
{
LSNode* p=head->next;
if(p==NULL)
{
cout<<"堆棧已空出錯(cuò)"<nex
32、t=p->next;
*d=p->data;
free(p);
return 1;
}//彈出棧頂元素
int StackTop(LSNode* head,DataType *d)
{
推薦精選
LSNode* p=head->next;
if(p==NULL)
{
cout<<"堆棧已空出錯(cuò)"<data;
return 1;
}
void Destroy(LSNode* head)
{
LSNode* p,*p1;
p=head;
while(p!=
33、NULL)
{
p1=p;
p=p->next;
free(p1);
}
}
void ExplsCorrect(char exp[]) //檢測(cè)輸入表達(dá)式的括號(hào)匹配函數(shù)
{
LSNode *head;
int i=0;
char c;
StackInitiate(&head);
while(exp[i]) //表達(dá)式?jīng)]讀完時(shí)，執(zhí)行'while'循環(huán)
{
if(exp[i]=='(')StackPush(head,exp[i]); //遇到左括號(hào)'('將其進(jìn)棧
34、 else if(exp[i]==')'&&StackNotEmpty(head)&&StackTop(head,&c)&&c=='(')StackPop(head,&c); //棧頂元素為'('且當(dāng)前元素為')'時(shí)，出棧，繼續(xù)讀下面的字符
else if (exp[i]==')'&&StackNotEmpty(head)&&StackTop(head,&c)&&c!='(')//棧頂元素不為'('且當(dāng)前元素為')'時(shí)，輸出'左右括號(hào)不匹配'，退出重新輸入
{
cout<<"左右括號(hào)配對(duì)次序不正確!"<
35、 if((exp[i]==')')&&!StackNotEmpty(head)) //當(dāng)前元素為')'但是堆棧已空時(shí)候，輸出
推薦精選
'右括號(hào)多于左括號(hào)'，退出程序重新輸入
{
cout<<"右括號(hào)多于左括號(hào)!"<
36、正確"<
#include
#include
#include
#include
typedef char DataType;
#include"value.h"
#include"Convert.h"
#include"ExplsCorrect.h"
void ma
37、in()
{
char a[500],b[500][100];
int i,j,n,End,flag,c[500],num=0; //c數(shù)組用來存放變量的真值
char m='y';
SeqStack1 S;
BiTreeNode *P;
cout<<"\t\t*********************************************"<
38、t<<"\t\t** * * * * * * * * * * **"<
39、******************************"<>a;
cout<<"\n檢測(cè)括號(hào)匹配:";
cout<<"\n-------------------------"<
40、
//測(cè)試輸出后序表達(dá)式//
cout<<"-------------------------"<
41、dl;
cout<<"\n\n構(gòu)造的二叉樹結(jié)構(gòu)為:"<
42、][0]))
推薦精選
{
num++;
}
}
while(1)
{
cout<<"\n\t\t 請(qǐng)為變量賦值<0:false or 1:true>\n"<
43、} //有重復(fù)變量時(shí)flag為1，且找到第一個(gè)重復(fù)變量b[j]
}
if(flag==0)
{
cout<<">>>>>請(qǐng)輸入上述表達(dá)式中的變量“"<>c[i];
cout<
44、把重復(fù)出現(xiàn)的變量都用第一次的值賦值
}
}
else c[i]=-1;
}
End=PostOrder(P,c,b,n);
cout<<"\n>>>>>該表達(dá)式的最后結(jié)果為："<>i;
if(i==0) break;
}
推薦精選
int v[100],p;
printf("真值表如下：\n");
End=0;
long count=(int)pow(2,num)
45、;
for(p=0;p
46、nd=PostOrder(P,c,b,n));
printf("\n");
v[num-1]++;
p=num-1;
while(v[p]>=2)
{
v[p]%=2;
v[p-1]++;
p--;
}
}
cout<<"\n'y':繼續(xù)下一個(gè)表達(dá)式的計(jì)算 'n':退出程序"<>m;
cout<<"\n\n";
}
}
推薦精選
（注：可編輯下載，若有不當(dāng)之處，請(qǐng)指正，謝謝!）
推薦精選
計(jì)算命題演算公式的真值
