数据结构--表达式翻译

#include#include#define TRUE 1#define FALSE 0#define MAXNUM 100typedef int DataType;struct SeqStack DataType sMAXNUM;int t;typedef struct SeqStack *PSeqStack;PSeqStack createEmptyStack_seq() PSeqStack pastack;pastack = (PSeqStack)malloc(sizeof(struct SeqStack);if (pastack = NULL)printf(Out of space!n);elsepastack-t = -1;return pastack; int isEmptyStack_seq(PSeqStack pastack) return pastack-t = -1; void push_seq(PSeqStack pastack, DataType x) if (pastack-t = MAXNUM - 1)printf(Overflow!n);else pastack-t = pastack-t + 1;pastack-spastack-t = x; void pop_seq(PSeqStack pastack) if (pastack-t = -1)printf(Underflow!n);elsepastack-t = pastack-t - 1; DataType top_seq(PSeqStack pastack) return pastack-spastack-t; int infixtoSuffix(const char * infix, char * suffix) /*将中缀表达式转换为后缀表达式，顺利转换返回true，若转换过程中发现中缀表达式非法则返回false*/int state_int = FALSE; /*state_int记录状态，等于true表示刚读入的是数字字符，等于false表示刚读入的不是数字字符，设置这个变量是为了在每输出一个整数后输出一个空格，以免连续输出的两个整数混在一起。*/char c, c2;PSeqStack ps = createEmptyStack_seq(); /*运算符栈*/int i, j = 0;if (infix0 = 0) return FALSE; /*不允许出现空表达式*/for (i = 0; infixi != 0; i+)c = infixi;switch (c) case : case t: case n:if (state_int = TRUE) suffixj+ = ;/*状态从true转换为false时输出一个空格*/state_int = FALSE;break; /*遇到空格或制表符忽略*/case 0: case 1: case 2: case 3: case 4:case 5: case 6: case 7: case 8: case 9:state_int = TRUE;suffixj+ = c; /*遇到数字输出*/break;case (:if (state_int = TRUE)suffixj+ = ;/*状态从true转换为false时输出一个空格*/state_int = FALSE;push_seq(ps, c); /*遇到左括号，入栈*/break;case ):if (state_int = TRUE) suffixj+ = ;/*状态从true转换为false时输出一个空格*/state_int = FALSE;c2 = );while (!isEmptyStack_seq(ps) c2 = top_seq(ps);/*取栈顶*/pop_seq(ps); /*出栈*/if (c2 = () break;suffixj+ = c2;if (c2 != () free(ps);suffixj+ = 0;return FALSE; break;case +: case -:if (state_int = TRUE) suffixj+ = ;state_int = FALSE;while(!isEmptyStack_seq(ps) c2 = top_seq(ps); if (c2 = + | c2 = - | c2 = * | c2 = /) pop_seq(ps);suffixj+ = c2;else if(c2=() break;push_seq(ps, c); break;case *: case /:if (state_int = TRUE) suffixj+ = ;state_int = FALSE;while (!isEmptyStack_seq(ps) c2 = top_seq(ps); if (c2 = * | c2 = /) pop_seq(ps);suffixj+ = c2; else if(c2=+|c2=-|c2=() break;push_seq(ps, c); break;default:free(ps);suffixj+ = 0;return FALSE;if (state_int = TRUE) suffixj+ = ;while (!isEmptyStack_seq(ps) c2 = top_seq(ps);pop_seq(ps); if (c2 = () free(ps);suffixj+ = 0;return FALSE; suffixj+ = c2; free(ps);suffixj+ = 0;return TRUE; int calculateSuffix(const char * suffix, int * presult) int state_int = FALSE; PSeqStack ps = createEmptyStack_seq(); int num = 0, num1, num2;int i;char c;for (i = 0; suffixi != 0; i+) c = suffixi;switch (c) case 0:case 1: case 2: case 3: case 4:case 5: case 6: case 7: case 8: case 9:if (state_int = TRUE) num = num * 10 + c - 0;else num = c - 0;state_int = TRUE;break;case : caset: case n:if (state_int = TRUE) push_seq(ps, num); state_int = FALSE;break;case +: case -: case *: case /:if (state_int = TRUE) push_seq(ps, num); state_int = FALSE;if (isEmptyStack_seq(ps) free(ps);return FALSE; num2 = top_seq(ps);pop_seq(ps);if (isEmptyStack_seq(ps) free(ps);return FALSE; num1 = top_seq(ps);pop_seq(ps);if (c = +) push_seq(ps, num1 + num2);if (c = -) push_seq(ps, num1 - num2);if (c = *) push_seq(ps, num1 * num2);if (c = /) push_seq(ps, num1 / num2);break;default: free(ps);return FALSE;*presult = top_seq(ps); pop_seq(ps);if (!isEmptyStack_seq(ps) free(ps);return FALSE; free(ps);return TRUE; void getline(char * line, int limit) char c;int i = 0;while (i limit - 1 & (c = getchar() != EOF & c != n)linei+ = c;linei = 0; void main() char c, infixMAXNUM, suffixMAXNUM;int result;int flag = TRUE;while (flag = TRUE) printf(请输入表达式!nInput:);getline(infix, MAXNUM); if(infixtoSuffix(infix, suffix) = TRUE)printf(suffix:%sn, suffix); else printf(无效的输入!n);printf(nContinue? (y/n);scanf(%c, &c);if (c = n | c = N) flag = FALSE;while (getchar() != n);printf(n);continue;if