#define ERROR 0
#define OK 1
#define STACK_INT_SIZE 10 /*存储空间初始分配量*/
#define Queue_Size 20
typedef int ElemType; /*定义元素的类型*/
typedef struct{
char Qdata[Queue_Size];
int front,rear;
}SeqQueue;
typedef struct{
ElemType *base;
ElemType *top;
int stacksize; /*当前已分配的存储空间*/
}SqStack;
SqStack OPTR, OPND;
SeqQueue SeQ;
char PreTab[7][7]={{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','x'},
{'>','>','>','>','x','>','>'},
{'<','<','<','<','<','x','='}
}; // 该矩阵中，X字符表示不存在优先关系，在分析过程查找到这个值，表示表达式有错。
char *OpretorS=\"+-*/()#\"; // 运算符集
char *Express=\"3*(7-2)-6*2\"; // 初始化的表达式
// 注意本程序只分析1位整数的表达式的运算，所以输入的表达式要注意！！
// 能力强的同学自己进行扩展：增加词法分析过程进行拼数。
int InitStack(SqStack *S); /*构造空栈*/
int push(SqStack *S,ElemType *e); /*入栈*/
int Pop(SqStack *S); /*出栈*/
void initQueue(SeqQueue *Q){/*队列初始化*/
Q->front=0;
Q->rear=0;
}
int EnterQueue(SeqQueue *Q,char c){ /*入队*/
if (Q->rear==Queue_Size)
{ printf(\"\\n队列满，无法入队！\\n\");return ERROR; }
Q->Qdata[Q->rear]=c;
Q->rear++;
return OK;
}
int OutQueue(SeqQueue *Q,char *e){ /*出队*/
if(Q->front==Q->rear)
{ printf(\"\\n队列空，无法出队！\\n\");return ERROR; }
*e=Q->Qdata[Q->front++];
return OK;
}
int InitStack(SqStack *S){
S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));
if(!S->base) return ERROR;
S->top=S->base;
S->stacksize=STACK_INT_SIZE;
return OK;
}/*InitStack*/
int Push(SqStack *S,ElemType e){
if ((S->top-S->base)>STACK_INT_SIZE) return 0;
*S->top=e;
S->top++;
return OK;
}
int Pop(SqStack *S){
int e;
if (S->top==S->base ) return 0;
S->top--;
e=*S->top;
return *S->top;
}
//判定c是否运算符，若是运算符则返回改运算符在运算符集中的位置，这样就能扫描优先//关系表，确定相邻运算符之间的优先级
int IsOps(char c){
int i=0;
char *p;
p=OpretorS;
while( )
{if (*p++==c) break;
i++;
}
return i;
}
char Precede(char c1,char c2){ //返回c1与c2运算符的优先关系
int i,j;
i=IsOps(c1);
j=IsOps(c2);
if ( ) return 0;
return PreTab[ ][ ];
}
int Operate(int a,char TheOp,int b){ //进行TheOp计算
switch ( ){
case '+': return a+b;
case '-': return ;
case '*': return ;
case '/': return ;
}
return 0;
}
int main(){
char *ScanChar;
char c1,c;
char TheOp;
int b,a,digit;
InitStack(&OPTR);
Push(&OPTR,'#');
InitStack(&OPND);
initQueue(&SeQ);
ScanChar=Express;
c=*ScanChar;
while(c!='#' || *OPTR.top!='#')
{ if (c==0) c='#';
if (IsOps(c)>=7) // 判定是否是运算符，若IsOps的值>=7，则c是操作数
{digit=c-'0'; // 将字符转换成相应的数值
Push(&OPND,digit); // 操作数入栈
EnterQueue(&SeQ,c); // 操作数入队
c=*++ ;
}
else
{ c1=*(OPTR.top-1);
Switch ( (c1,c)) // 调用哪个函数
{case '<':
Push(&OPTR,c);
c=*++ScanChar;
break;
case '=': //脱括号
TheOp=Pop(&OPTR);
if (c!=0 && c!='#')
c=*++ScanChar;
break;
case '>':
TheOp=Pop (& ); // 参与计算的运算符出栈
EnterQueue(&SeQ,TheOp); // 参与运算的运算符入队
b=Pop(&OPND);
a=Pop(&OPND);
Push(&OPND, (a,TheOp,b));
break;
default:
printf(\"\\n算术表达式错误！\\n\") ;
return ERROR ;
}
}
}
printf(\"\\n算术表达式：%s --->后缀表达式为：\
while( ) // 将队列输出即为表达式的后缀形式
{ OutQueue(&SeQ,&c);printf(\"%c\
printf(\"\\n其结果为：%d\ )); // 输出表达式的值
return 0;
}
