#include <stdio.h>
#include <stdlib.h>
#include "sqstack.h"
void InitStack(SqStack &S,int stacksize){
//构造一个空栈
S.base=(SElemType *)malloc(stacksize*sizeof(SElemType));
if(!S.base)
exit(1);
S.top=S.base;
S.stacksize=stacksize;
}
void DestroyStack(SqStack &S){
//销毁栈
free(S.base);
S.base=S.top=NULL;
S.stacksize=0;
}
void ClearStack(SqStack &S){
//把栈设置为空栈
S.top=S.base;
}
Status EmptyStack(SqStack S){
//判空栈
if(S.base==S.top)
return TRUE;
else
return FALSE;
}
int StackLength(SqStack S){
//求栈长
return S.top-S.base;
}
Status GetTop(SqStack S,SElemType &e){
//返回栈顶元素
if(EmptyStack(S))
return ERROR;
e=*(S.top-1);
return OK;
}
void Push(SqStack& S,SElemType e){
//入栈
if(S.top-S.base>=S.stacksize){
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)
exit(1);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
}
Status Pop(SqStack &S,SElemType &e){
//出栈
if(EmptyStack(S))
return ERROR;
e=*--S.top;
return OK;
}
void StackTraverse(SqStack S){
//打印
SElemType *p;
int n;
printf("栈空间为：%d\n",S.stacksize);
n=StackLength(S);
printf("栈元素个数为：%d\n",n);
if(n){
printf("(");
for(p=S.top-1;p>=S.base;p--){
printf("%d ",*p);
}
printf(")\n");
}
else printf("()\n");
}
#include<iostream>
#include<cstdlib>
#include<iomanip>
#define MAX 50
using namespace std;
char infix_q[MAX]; //用存存放中序表示法
//运算符优先级的比较，若输入运算符小于堆栈中的运算符则返回值1,否则返回0
int compare(char stack_o,char infix_o)
{
//在中序表示法队列及暂存堆栈中，运算符的优先级顺序表
//其优先值为 INDEX/2
char infix_priority[9];
char stack_priority[8];
int index_s=0,index_i=0;
infix_priority[0]='q';infix_priority[1]='}';
infix_priority[2]='+';infix_priority[3]='-';
infix_priority[4]='*';infix_priority[5]='/';
infix_priority[6]='^';infix_priority[7]=' ';
infix_priority[8]='(';
stack_priority[0]='q';stack_priority[1]='(';
stack_priority[2]='+';stack_priority[3]='-';
stack_priority[4]='*';stack_priority[5]='/';
stack_priority[6]='^';stack_priority[7]=' ';
while (stack_priority[index_s]!=stack_o)
index_s++;
while (infix_priority[index_i]!=infix_o)
index_i++;
return ((int) (index_s/2)>=(int) (index_i/2) ? 1:0);
}
//中序转前序的方法
void infix_to_postfix()
{
int rear=0,top=0,flag=0,i=0;
char stack_t[MAX];
for (i=0;i<MAX;i++)
stack_t[i]='\0';
gets(infix_q);
i=0;
while (infix_q[i]!='\0')
{
i++;
rear++;
}
infix_q[rear]='q'; //队列加入q为结符号
cout<<"\t"<<"后序表示法:";
stack_t[top]='q';
for (flag=0;flag<=rear;flag++) //堆栈加入q为结束符号
{
switch (infix_q[flag])
{ //输入为"}"，则输出堆栈内运算符，直到堆栈内为"("
case ')':
while (stack_t[top]!='(')
cout<<setw(1)<<stack_t[top--];
top--;
break;
//输入q，则将堆栈内还未输出的运算符输出
case 'q':
while (stack_t[top]!='q')
cout<<setw(1)<<stack_t[top--];
break;
//输入为运算符，若不于TOP在堆栈中所指运算符
//则将堆栈所指运算符输出,若大于TOP在堆栈中
//所指运算符，则将输入的运算符放入栈中
case '(':
case '^':
case '*':
case '/':
case '+':
case '-':
while (compare(stack_t[top],infix_q[flag])==1)
cout<<setw(1)<<stack_t[top--];
stack_t[++top]=infix_q[flag];
break;
//输入为运算符对象,则直接输出
default:
cout<<setw(1)<<infix_q[flag];
break;
}
}
}
//主函数声明
int main(void)
{
int i=0;
for (i=0;i<MAX;i++)
infix_q[i]='\0';
cout<<"\t============================================"<<endl;
cout<<"\t本程序会将其转成后序表达式"<<endl;
cout<<"\t请输入中序表达式子"<<endl;
cout<<"\t例如:(9+3)*8+7*6-8/4"<<endl;
cout<<"\t可以使用的运算符包括:^,*,+,-,/,(,)等"<<endl;
cout<<"\t============================================"<<endl;
cout<<"\t请开始输入中序表达式:";
infix_to_postfix();
cout<<endl;
cout<<"\t============================================"<<endl;
system("pause");
return 0;
}
有问题请回复~ ^ _ ^