大学数据结构无括号算术表达式处理算法

#defineTRUE1

#defineFALSE0

#defineStack_Size50

/*顺序栈-整型*/

typedefstruct

(

intelem[Stack_Size];/*用来存放栈中元素的一维

数组*/

inttop;/*用来存放栈顶元素的下标，

top为-1表示栈是空栈*/

JnStack;

/*初始化*/

voidnInitStack(nStack*S)

(

/*构造一个空栈S*/

S->top=-l;

/*判栈空*/

intnIsEmpty(nStack*S)/*判断栈S为空栈时返回值

为真，反之为假*/

(

return(S->top==-l?TRUE:FALSE);

/*判栈满*/

intnIsFull(nStack*S)/*判断栈S为满栈时返回值为

真，反之为假*/

(

return(S->top==Stack_Size-l?TRUE:FALSE);

intnPush(nStack*S,intx)

(

if(S->top==Stack_Size-l)return(FALSE);/*栈已

满*/

S->top++;

S->elem[S->top]=x;

return(TRUE);

intnPop(nStack*S,int*x)

{/*将栈S的栈顶元素弹出，放到x所指的存储空

间中*/

if(S->top==-l)/*栈为空*/

return(FALSE);

else

(

*x=S->elem[S->top];

S->top-;/*修改栈顶指针*/

return(TRUE);

intnGetTop(nStack*S,int*x)

{/*将栈S的栈顶元素弹出，放到x所指的存储空

间中，但栈顶指针保持不变*/

if(S->top==-l)/*栈为空*/

return(FALSE);

else

(

*x=S->elem[S->top];

return(TRUE);

/*顺序栈-字符型*/

typedefstruct

(

charelem[Stack_Size];/*用来存放栈中元素的一

维数组*/

inttop;/*用来存放栈顶元素的下标，

top为-1表示栈是空栈*/

}strStack;

/*初始化*/

voidstrInitStack(strStack*S)

(

/*构造一个空栈S*/

S->top=-l;

)

/*判栈空*/

intstrlsEmpty(strStack*S)/*判断栈S为空栈时返回

值为真，反之为假*/

return(S->top==-l?TRUE:FALSE);

)

/*判栈满*/

intstrIsFull(strStack*S)/*判断栈S为满栈时返回值

为真，反之为假*/

(

return(S->top==Stack_Size-l?TRUE:FALSE);

)

charstrPush(strStack*S,charx)

(

if(S->top==Stack_Size-l)return(FALSE);/*栈已

满*/

S->top++;

S->elem[S->top]=x;

return(TRUE);

charstrPop(strStack*S,char*x)

{/*将栈S的栈顶元素弹出，放到X所指的存储空

间中*/

if(S->top==-l)/*栈为空*/

return(FALSE);

else

(

*x=S->elem[S->top];

S->top-;/*修改栈顶指针*/

return(TRUE);

)

)

intstrGetTop(strStack*S,char*x)

{/*将栈S的栈顶元素弹出，放到x所指的存储空

间中，但栈顶指针保持不变*/

if(S->top==-l)/*栈为空*/

return(FALSE);

else

(

*x=S->elem[S->top];

return(TRUE);

/*功能函数*/

intMatch(charch,charstr)

if(ch=(&&str==')')

(

returnTRUE;

)

elseif(ch=='['&&str==*]1)

(

returnTRUE;

)

elseif(ch=='{'&&str=='}')

(

returnTRUE;

)

elsereturnFALSE;

intIn(charch)

if(ch=='+')

returnTRUE;

)

elseif(ch=='-')

(

returnTRUE;

)

elseif(ch=='*')

(

returnTRUE;

)

elseif(ch==7')

(

returnTRUE;

)

elseif(ch=='(')

(

returnTRUE;

elseif(ch==')')

returnTRUE;

)

elseif(ch=='#')

(

returnTRUE;

)

elsereturnFALSE;

charCompare(charx,charch)

(

switch(x)

(

case

if(ch=-+'||ch=='-'||ch—')'||ch=='#')

return

elseif(ch-'*'||ch-7'||ch-'(')

return

break;

case

if(ch=-+'||ch=='-'||ch==')'||ch=='#')

return

elseif(ch=='*'||ch==7'||ch=-(')

return

break;

case

if(ch='(')

(

return

)

else

(

return

)

break;

case7':

if(ch=='(')

return

else

return

break;

case

if(ch-"+'||ch='-'||ch—'*'||ch=-/|||ch-'(')

return

elseif(ch==')')

return

elseif(ch==*#')

return'O';

break;

case

if(ch=-+'||ch=='-'||ch—'*'||ch==7'||ch==')'||ch=='#')

return

elseif(ch==,(')

return'O';

break;

case

if(ch=='+'||ch=--'||ch==**'||ch=7'||ch=='(')

return

elseif(ch=='#')

return

elseif(ch—),)

return'O';

break;

default:

return'O';

break;

intExecute(inta,charop,