栈和队列的应用

1表达式求值

表达式求值的是一个栈应用的典型例子，通常称为运算符优先算法，实现该算法需要使用两个工作栈，一个称为OPTR，存储运算符，一个称为OPND，存储操作数或者运算结果。算法基本思想：
1：首先置工作栈为空栈，表达式起始符“#”为运算符栈的栈底元素。
2：依次读入表达式的每一个字符，若是操作数则进入OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先级后作出相应操作，直到整个表达式求值完毕。

下表为运算符的优先级关系表：

	+	-	*	/	(	)	#
+	>	>	<	<	<	>	>
-	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	<	<	<	<	<	=
)	>	<	>	>		>	>
#	<	<	<	<	<		=

OperandType EvaluateExpression() {
    //OP为运算符集合
    InitStack(OPTR);
    Push(OPTR, '#');
    InitStack(OPND);
    c = getchar();
    while (c != '#' || GetTop(OPTR) != '#') {
        if (!(In(c, OP))) {//不是运算符则进栈
            Push(OPND, c);
            c = getchar();
        } else {
            switch (Precede(GetTop(OPTR), c)) {//判断运算符优先级
                    case '<'://栈顶优先级底
                        Push(OPTR, c);
                        c = getchar();
                        break;
                    case '='://脱括号并接受下一个字符
                        Pop(OPTR, x);
                        c = getchar();
                        break;
                    case '>'://退栈并将结果入栈
                        Pop(OPTR, theta);
                        Pop(OPND, b);
                        Pop(OPND，a);
                        Push(OPND, Operate(a, b, theta));
                        break;      
            }
        }
    }
    return GetTop(OPND);
}

2一元多项式加法运算

算法思路：
采用不带头结点的单向链表，按照指数递减的顺序排列各项。相同指数的项系数相加，其余部分进行拷贝。
两个指针P1和P2分别指向这两个多项式的第一个节点，不断循环。
（1）P1->expon == P2->expon:系数相加，若结果不为0，则作为结果多项式对应项的系数。同时P1和P2都分别指向下一项；
（2）P1->expon > P2->expon:将P1的当前项存入结果多项式，并使P1指向下一项；
（3）P1->expon < P2->expon:将P2的当前项存入结果多项式，并使P2指向下一项；
当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去。

代码：

struct PolyNode {
    int coef; //系数
    int expon; //指数
    struct PolyNode *link; //指向下一个节点的指针
};
typedef struct PoluNode *Polynimial;
Polynimial P1,P2;

 Polynomial PolyAdd (Polynomial P1, Polynomial P2) {
    Polynomial front, rear, temp;
    int sum;
    rear = (Polynomial) malloc(sizeof(struct PolyNode)); 
    front = rear; /* 由front 记录结果多项式链表头结点 */
        while ( P1 && P2 ) /* 当两个多项式都有非零项待处理时 */ 
            switch ( Compare(P1->expon, P2->expon) ) { 
                case 1:
                    Attach( P1->coef, P1->expon, &rear); 
                    P1 = P1->link;
                    break;
                case -1:
                    Attach(P2->coef, P2->expon, &rear); 
                    P2 = P2->link;
                    break;
                case 0:
                    sum = P1->coef + P2->coef;
                    if ( sum ) Attach(sum, P1->expon, &rear); 
                    P1 = P1->link;
                    P2 = P2->link;
                    break;
}
/* 将未处理完的另一个多项式的所有节点依次复制到结果多项式中去 */         
    for ( ; P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear);
    for ( ; P2; P2 = P2->link ) Attach(P2->coef, P2->expon, &rear); 
    rear->link = NULL;
    temp = front;
    front = front->link; /*令front指向结果多项式第一个非零项 */ 
    free(temp); /* 释放临时空表头结点 */
    return front;
}

void Attach( int c, int e, Polynomial *pRear ) {
    /* 由于在本函数中需要改变当前结果表达式尾项指针的值，*/ 
    /* 所以函数传递进来的是结点指针的地址，*pRear指向尾项*/
    Polynomial P;
    P =(Polynomial)malloc(sizeof(struct PolyNode)); /* 申请新结点 */ 
    P->coef = c; /* 对新结点赋值 */
    P->expon = e;
    P->link=NULL;
    /* 将P指向的新结点插入到当前结果表达式尾项的后面 */ 
    (*pRear)->link = P;
    *pRear = P; /* 修改pRear值 */
}