1-2-1.c

2005软件工程师考试下午编程题源代码

/*中国系统分析员顾问团，http://www.csai.cn*/
/*程序员下午考试指南书籍源码*/

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

typedef struct node{    /*符号、内部编号、优先级和后继栈元指针*/
char data; int code; int pri;
struct node *link;
}NODE;

struct Tb1{   /*符号、内部编号、优先级*/
char data; int code ; int  pri;
}opchTb1[] = {{'*', 1, 4}, {'/', 2, 4}, {'+', 3, 2}, {'-', 4, 2},
              {'(', 5, 5}, {')', 6, 1},{'\0', 7, 0}, {'#',-1, 0}};

    NODE *optop;   /*栈顶指针*/
    char num[200], *numtop;  /*工作数组和存储指针*/
char expStr[200];   /*存储中缀表达式的字符数组*/

    void push(char x, int c, int p, NODE **toppt){   /*链接存储栈的进栈函数*/
       NODE *q = (NODE *)malloc(sizeof(NODE));
       q->data = x; q->code = c; q->pri = p; q->link = *toppt; *toppt = q;
}

    int pop(char *op, int *cp, NODE **toppt) {  /*链接存储栈的出栈函数*/
       NODE *q = *toppt;
       if (*toppt == NULL) return 1;  /*空栈 */
       *op = q->data; *cp =q->code; *toppt = q->link ; free(q); return 0;
}
    int expr(char *pos){
       struct Tb1 *op; char sop; int type, code, n, m, i, c;
       optop = NULL; numtop = num; n = m = 0; c = ' ';
       push('#', 0, 0, &optop);  /*预先在栈中置一个0优先级的符号 */
while (1) {
	while (c == ' ' || c == '\t') c = *pos++; /*掠过空白符 */
		  if (isalpha(c)) {    /*复制变量名到工作数组*/
				  *numtop++ = ' ';
				  while (isalpha(c) || isdigit(c)) {*numtop++ = c ; c = *pos++; }
				  if (m) return 1;   /*运算符个数与运算分量个数不相容 */
				  m = 1;   /*运算分量比运算符多1 个 */
				  continue;
			  }
	else {   /*处理运算符或非法字符 */
			for (i = 0; opchTb1[i].code != -1 && opchTb1[i].data != c; i++);
				  if (opchTb1[i].code == -1) return 3;  /*非法字符 */
			  op = &opchTb1[i];
			  type = opchTb1[i].code;  /*得到运算符的内部码 */
				  c = *pos++;  /*C 中存储下一个字符*/
       		}
       		if (type < 5) {   /*如是运算符 */
           		if(m != 1) return 1;  /*运算符个数与运算分量个数不相容*/
           		m = 0;  /*运算符与运算分量一样多 */
       		}
       		if (type == 5) n++;  /*左括号计数增1*/
	if (type == 6) 
			if (n-- == 0) return 2;   /*圆括号不匹配*/
       			if  ( op->pri > optop->pri )   /*运算符或括号进栈 */
					if (op->data == '(' ) push(op->data,op->code, 1,&optop);
					else push(op->data, op->code, op->pri, &optop);
       			else {
					while (optop != NULL && op->pri <= optop->pri) {
                  			pop( &sop, &code, &optop );
							if ( code < 5 && code > 0) {   /* 运算符复制到工作数组*/
								*numtop++ = ' ';
								*numtop++ = sop;
                  				}
              		}
               		if (op->data == '\0')
						return (n != 0 || (m != 1 && numtop > num)) ? 4:( *numtop = '\0');
               		else if(op->data != ')')
                     		push (op->data, op->code, op->pri, &optop);
				}
       		
	}
}
void main(){ 
	int d;
printf("请输入表达式!\n");
gets(expStr);
       if ((d = expr(expStr)) == 0) printf("后缀表达式为 %s\n",num);
       else printf("表达式句法错！错误类型为%d\n",d);
}