《数据结构》课程设计报告书课程题目：表达式求值问题一.需求分析（1）以字符序列的形式从终端输入语法正确的不含变量的整数表达式，将该中缀表达式转换为后缀表达式。

（2）实现对后缀表达式的求值。

（3）演示在求值过程中运算符栈，操作数栈，输入字符和主要操作的变化过程。

二.概要设计表达式求值的算法分为两步进行：首先将中缀表达式转换为后缀表达式，再求后缀表达式的值。

（1）将中缀表达式转换为后缀表达式，对于字符串形式的合法的中缀表达式，“（”的运算优先级最高，“*”次之，“+”，“—”最低，同级运算符从左到右按顺序运算。

转化过程算法描述如下：从左到右对中缀表达式进行扫描，每次处理一个字符。

若遇到左括号入栈。

如遇到数字，原样输出。

若遇到运算符，如果它的优先级比栈顶元素优先级高，则直接入栈，否则栈顶元素出栈，直到新栈顶数据元素的优先级比它低，然后将它直接入栈。

重复以上步骤，直到表达式结束。

若表达式已全部结束，将栈顶元素全部出栈。

（2）后缀表达式求值算法描述如下：从左到右对后缀表达式进行扫描，每次处理一个字符。

若遇到数字，转化为整数，入栈。

若遇到运算符，出栈两个值进行运算，运算结果再入栈。

重复以上步骤，直到表达式结束，栈中最后一个数据元素就是所求表达式的结果。

三.详细设计#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define MAXNUM 100typedef 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");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->s[pastack->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->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("请输入表达式:\nInput:");getline(infix, MAXNUM);if(infixtoSuffix(infix, suffix) == TRUE)printf("suffix:%s\n", 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(calculateSuffix(suffix, &result) == TRUE)printf("Result:%d\n", result);elseprintf("输入有错误!\n");printf("\n是否继续? (y/n)");scanf("%c", &c);if (c == 'n' || c == 'N') flag = FALSE;while (getchar() != '\n');printf("\n");}}四.调试分析(1) 用栈的结构来解决表达式的求值，首先要解决的问题是如何将人们习惯书写的中缀表达式转换成计算机容易处理的后缀表达式。