#include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define MAXNUM 100 typedef int DataType; struct SeqStack { DataType s[MAXNUM]; 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"); else pastack->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->s[pastack->t] = x; } } void pop_seq(PSeqStack pastack) { if (pastack->t == -1) printf("Underflow!\n"); else pastack->t = pastack->t - 1; } DataType top_seq(PSeqStack pastack) { return pastack->s[pastack->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 (infix[0] == '\0') return FALSE; /*不允许出现空表达式*/ for (i = 0; infix[i] != '\0'; i++) { c = infix[i]; switch (c) { case ' ': case '\t': case '\n': if (state_int == TRUE) suffix[j++] = ' ';/*状态从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; suffix[j++] = c; /*遇到数字输出*/ break; case '(': if (state_int == TRUE) suffix[j++] = ' ';/*状态从true转换为false时输出一个空格*/ state_int = FALSE; push_seq(ps, c); /*遇到左括号，入栈*/ break; case ')': if (state_int == TRUE) suffix[j++] = ' ';/*状态从true转换为false时输出一个空格*/ state_int = FALSE; c2 = ')'; while (!isEmptyStack_seq(ps)) { c2 = top_seq(ps);/*取栈顶*/ pop_seq(ps); /*出栈*/ if (c2 == '(') { break; } suffix[j++] = c2; } if (c2 != '(') { free(ps); suffix[j++] = '\0'; return FALSE; } break; case '+': case '-': if (state_int == TRUE) suffix[j++] = ' '; state_int = FALSE; while(!isEmptyStack_seq(ps)) { c2 = top_seq(ps); if (c2 == '+' || c2 == '-' || c2 == '*' || c2 == '/') { pop_seq(ps); suffix[j++] = c2; } else if(c2=='(') break; } push_seq(ps, c); break; case '*': case '/': if (state_int == TRUE) suffix[j++] = ' '; state_int = FALSE; while (!isEmptyStack_seq(ps)) { c2 = top_seq(ps); if (c2 == '*' || c2 == '/') { pop_seq(ps); suffix[j++] = c2; } else if(c2=='+'||c2=='-'||c2=='(') break; } push_seq(ps, c); break; default: free(ps); suffix[j++] = '\0'; return FALSE; } } if (state_int == TRUE) suffix[j++] = ' '; while (!isEmptyStack_seq(ps)) { c2 = top_seq(ps); pop_seq(ps); if (c2 == '(') { free(ps); suffix[j++] = '\0'; return FALSE; } suffix[j++] = c2; } free(ps); suffix[j++] = '\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; suffix[i] != '\0'; i++) { c = suffix[i]; 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 ' ': case'\t': 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') line[i++] = c; line[i] = '\0'; } void main() { char c, infix[MAXNUM], suffix[MAXNUM]; int result; int flag = TRUE; while (flag == TRUE) { printf("Plese input an infix expression!\nInput:"); getline(infix, MAXNUM); if(infixtoSuffix(infix, suffix) == TRUE) printf("suffix:%s\n", suffix); else { printf("Invalid infix!\n"); printf("\nContinue? (y/n)"); scanf("%c", &c); if (c == 'n' || c == 'N') flag = FALSE; while (getchar() != '\n'); printf("\n"); continue; } if(calculateSuffix(suffix, &result) == TRUE) printf("Result:%d\n", result); else printf("Invalid suffix!\n"); printf("\nContinue? (y/n)"); scanf("%c", &c); if (c == 'n' || c == 'N') flag = FALSE; while (getchar() != '\n'); printf("\n"); } }