从中缀向后缀转换表达式(15分)
Grade: 15 / Discount: 0.8
问题描述:
中缀表达式就是我们通常所书写的数学表达式,后缀表达式也称为逆波兰表达式,在编译程序对我们书写的程序中的表达式进行语法检查时,往往就可以通过逆波兰表达式进行。我们所要设计并实现的程序就是将中缀表示的算术表达式转换成后缀表示,例如,
将中缀表达式
(A 一 (B*C 十 D)*E) / (F 十 G )
转换为后缀表示为
ABC*D 十 E*—FG 十/
注意 : 为了简化编程实现,假定变量名为正实数,运算符只有+,-,* 和/,可以处理界限符 ,并假定输入的算术表达式正确。
要求:使用栈数据结构实现 ,输入的中缀表达式以#号结束
输入:
整数N。表示下面有N个中缀表达式
N个由正实数和运算符构成的表达式
输出
N个后缀表达式。操作数和操作符之间以空格隔开。
#include <stdio.h> #include <stdlib.h> struct shu{ int front; int rear; }OPND; struct others { char * base; char * top; int size; }OPTR; char bijiao(char x, char y) { if (x == '+') { if (y == '+' || y == '-' || y == ')' || y == '#') return('>'); else return('<'); } if (x == '-') { if (y == '+' || y == '-' || y == ')' || y == '#') return('>'); else return('<'); } if (x == '*') { if (y == '(') return('<'); else return('>'); } if (x == '/') { if (y == '(') return('<'); else return('>'); } if (x == '(') { if (y == ')') return('='); if (y == '+' || y == '-' || y == '*' || y == '/' || y == '%' || y == '(') return('<'); } if (x == ')') { if (y == '+' || y == '-' || y == '*' || y == '/' || y == '%' || y == ')' || y == '#') return('>'); } if (x == '#') { if (y == '+' || y == '-' || y == '*' || y == '/' || y == '%' || y == '(') return('<'); if (y == '#') return('='); } } void main() { int n, i, j, k, s[50], flag; char sopnd[50][50], str[50],t; scanf("%d", &n); getchar(); for (i = 0;i < n;i++) { flag = 0; OPND.front = 0; OPND.rear = 0; OPTR.size = 50; OPTR.base = (char *)malloc(OPTR.size * sizeof(char)); OPTR.top = OPTR.base; *OPTR.top++ = '#'; for (j = 0;j < 50;j++) s[j] = 0; gets(str); for (j = 0;str[j] != '#' || *(OPTR.top - 1) != '#';j++) { if (str[j] >= '0' && str[j] <= '9') { for (k = 0;(str[j] <= '9' && str[j] >= '0') || str[j] == '.';) { sopnd[OPND.rear][k] = str[j]; j++; k++; } sopnd[OPND.rear][k] = '\0'; OPND.rear++; j--; } else { t= bijiao(*(OPTR.top - 1), str[j]); { if(t=='<') { *OPTR.top++ = str[j]; } if(t=='='){ OPTR.top--; } if(t=='>') { for (;OPND.front < OPND.rear;OPND.front++) { if (flag == 1) printf(" %s", sopnd[OPND.front]); else printf("%s", sopnd[OPND.front]); flag = 1; } printf(" %c", *--OPTR.top); j--; } } } } printf("\n"); } }