表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。假设操作数是正整数，运算符只含有加“+”、减“-”、乘“*”、除“/”四种二元运算符，界限符有左括号“(”、右括号“)”和表达式起始、结束符“#”。利用运算符优先法对算术表达式求值。

        在计算机中，由于不同的运算符具有不同的优先级，又要考虑括号，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。以字符列的形式从终端输入语法正确的、不含变量的整数表达式。利用已知的运算符优先关系，实现对算术四则混合运算表达式的求值。

（1）主函数模块：

接收算数表达式，根据判断优先级函数返回值选择后续操作并输出结果。

（2）栈的基本操作模块：

包括栈的初始化、入栈、出栈、获取栈顶元素。

（3）判断运算符操作数模块：

判断用户输入的字符为运算符或操作数，进行分类操作。

（4）判断优先级模块：

判断输入符号和操作符栈顶元素的优先级。‘*’‘/’高于‘+’‘-’，‘（’高于‘+’‘-’‘*’‘/’，‘）’低于‘+’‘-’‘*’‘/’，‘#’低于所有运算符，当‘（’‘）’及‘#’‘#’相遇则返回‘=’，‘）’‘（’、‘#’‘）’、‘（’‘#’相遇则返回特殊符号‘！’判定用户输入语法错误。

（5）表达式求值模块：

取操作符栈顶元素及两个操作数栈顶元素进行运算.

图2-1 系统流程图

表达式求值算法在使用栈的过程中元素个数变化较小，故使用顺序栈实现。

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时附设指针top指示栈顶元素在顺序栈中的位置。本程序中初始化了三个顺序栈，分别存放操作数、运算符及组成多位数的数值，通过栈后进先出的特点实现表达式的计算。

程序中定义了结构体变量OPTR和OPND分别存放运算符和操作数，结构体变量中包含三个元素，指向栈底的指针base，指向栈顶的指针top和存放当前顺序栈可使用的最大容量，定义如下所示：

typedef struct {                //寄存运算符char* base;                //栈底指针char* top;                         //栈顶指针int stacksize;               //当前可使用最大容量}OPTR;typedef struct {                //寄存操作数double* base;double* top;int stacksize;}OPND;

（1）初始化栈函数：

int InitStack(OPTR* s);int InitStack(OPND* s);

实现功能：初始化顺序栈。

（2）入栈函数：

int Push(OPTR* s, char e);int Push(OPND* s, double e);

实现功能：将元素e推入栈中，存储于栈顶。

（3）出栈函数：

int Pop(OPTR* s, char* e);int Pop(OPND* s, double* e);

实现功能： 如果栈不为空则删除栈顶元素并赋值给e。

（4）获取栈顶元素函数：

char Gettop(OPTR* s);double Gettop(OPND* s);

实现功能：如果栈不为空则返回栈顶元素给e。

（5）判断字符类型函数：

int In(char e);

实现功能：判断字符类型为运算符或操作数，运算符返回值为1，操作数返回值为0；

（6）比较运算符优先级函数：

char Precede(char a, char b);

实现功能：比较操作符栈顶元素和最新接收的操作符的优先级

（7）计算函数：

double Operate(double a, double b, char t);

实现功能：取操作符栈顶元素及两个操作数栈顶元素进行运算。

（8）主函数：

int main()；

实现功能：接收用户输入字符并根据优先级函数返回值选择后续操作，并输出运算结果。

#include#include#define STACK_SIZE 10              //存储空间初始分配量#define STACK_INCREASE 5    //存储空间分配增量typedef struct {                //寄存运算符char* base;           //栈底指针char* top;                  //栈顶指针int stacksize;        //当前可使用最大容量}OPTR;typedef struct {                //寄存操作数double* base;double* top;int stacksize;}OPND;int InitStack(OPTR* s);int InitStack(OPND* s);int Push(OPTR* s, char e);int Push(OPND* s, double e);int Pop(OPTR* s, char* e);int Pop(OPND* s, double* e);char Gettop(OPTR* s);double Gettop(OPND* s);int In(char e);char Precede(char a, char b);double Operate(double a, double b, char t);//主函数int main(){OPTR optr;OPND opnd;OPND temp;    //临时存储数字，构造多位数char c;            //接收表达式char y;            //接收脱掉的括号和井号char theta;       //接收脱出进行运算的运算符double a, b;  //接收脱出进行运算的操作数int g = 1;while(g){system("cls");printf("1运行计算器 0退出程序");scanf("%d",&g);getchar();if(g){                       double x = 0, z = 0;    //多位数转换int n = 1;                   //幂int error = 0;               //输入格式错误则报错InitStack(&optr);InitStack(&opnd);InitStack(&temp);printf("请输入整数表达式（以#结束）：\n");Push(&optr, '#');c = getchar();while (c != '#' || Gettop(&optr) != '#'){if (c == '0') {Push(&opnd, (double)z);c = getchar();}else{while (!In(c)){                                               //将多位数存入临时栈Push(&temp, c - '0');       //字符转数字c = getchar();}while (temp.base != temp.top){                                 //将临时栈中的数重组为多位数Pop(&temp, &x);z = z + x * n;n *= 10;}n = 1;if (z)Push(&opnd, (double)z);//重组后的多位数入栈z = 0;}if (In(c)){switch (Precede(Gettop(&optr), c)){case '<':Push(&optr, c);c = getchar();break;case '=':Pop(&optr, &y);c = getchar();break;case '>':Pop(&optr, &theta);Pop(&opnd, &b);Pop(&opnd, &a);Push(&opnd, Operate(a, b, theta));break;case '!':printf("输入错误！");error = 1;break;}}if (error)break;}if (!error)printf("结果为：%.2f\n", Gettop(&opnd));system("pause");}else break;   }return 0;}//构造空栈sint InitStack(OPTR* s) {s->base = (char*)malloc(STACK_SIZE * sizeof(char));if (!s->base)exit(0);//存储分配失败s->top = s->base;s->stacksize = STACK_SIZE;return 1;}int InitStack(OPND* s) {s->base = (double*)malloc(STACK_SIZE * sizeof(double));if (!s->base)exit(0);s->top = s->base;s->stacksize = STACK_SIZE;return 1;}//插入元素e为新的栈顶int Push(OPTR* s, char e) {if (s->top - s->base >= s->stacksize) {//栈满，追加存储空间s->base = (char*)realloc(s->base,(s->stacksize + STACK_INCREASE) * sizeof(char));if (!s->base)exit(0);s->top = s->base + s->stacksize;s->stacksize += STACK_INCREASE;}*(s->top) = e;s->top++;}int Push(OPND* s, double e) {if (s->top - s->base >= s->stacksize) {s->base = (double*)realloc(s->base,(s->stacksize + STACK_INCREASE) * sizeof(double));if (!s->base)exit(0);s->top = s->base + s->stacksize;s->stacksize += STACK_INCREASE;}*(s->top) = e;s->top++;}//删除栈顶元素,返回其值int Pop(OPTR* s, char* e) {if (s->top == s->base)return 0;s->top--;*e = *(s->top);return 1;}int Pop(OPND* s, double* e) {if (s->top == s->base)return 0;s->top--;*e = *(s->top);return 1;}//判断栈是否为空，不为空则返回栈顶元素echar Gettop(OPTR* s) {if (s->top == s->base)return 0;char* e = s->top;e--;return *e;}double Gettop(OPND* s) {if (s->top == s->base)return 0;double* e = s->top;e--;return *e;}//判断是否为运算符int In(char e) {if (e == '+' || e == '-' || e == '*' || e == '/' || e == '(' || e == ')' || e == '#')return 1;else return 0;}//判断优先级char Precede(char a, char b) {if (a == '+'){if (b == '*' || b == '/' || b == '(') return '<';else return '>';}else if (a == '-'){if (b == '*' || b == '/' || b == '(') return '<';else return '>';}else if (a == '*'){if (b == '(')return '<';else return '>';}else if (a == '/'){if (b == '(')return '<';else return '>';}else if (a == '('){if (b == ')')return '=';else if (b == '#') return '!';else return '<';}else if (a == ')'){if (b == '(')return '!';else return '>';}else if (a == '#'){if (b == ')')return '!';if (b == '#')return '=';else return '<';}}//计算double Operate(double a, double b, char theta) {switch (theta){case '+':return a + b;case '-':return 1.0 * a - b;case '*':return a * b;case '/':if (b != 0)return 1.0 * a / b;elseprintf("输入错误！");exit(0);}}

（1）提示开始页面：

提示用户选择进行计算操作或退出程序，提示界面如图4-1所示。

图4-1 开始界面视图

（2）输入表达式界面：

提示用户输入表达式并以#结束，提示界面如图4-2所示。

图4-2 提示输入界面视图 

（3）输出结果界面：

输出用户输入表达式的计算结果并提示下一步操作，输出结果界面如图4-3所示。

图4-3 输出界面视图

(1)个位数加减乘除混合运算结果如图5-1所示。

图5-1 个位数测试结果图

(2)多位数加减乘除混合运算结果如图5-2所示。

图5-2 多位数测试结果图

(3)当输入语法有错误时出现提示（‘）’‘（’、‘#’‘）’或‘（’‘#’相遇），提示界面如图5-3所示。

图5-3 语法错误提示图1

(4)当计算中出现除数为零情况出现提示，提示界面如图5-4所示。

图5-4 语法错误提示图2

这次数据结构课程设计，使我了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力，初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能，提高综合运用所学的理论知识和方法独立分析和解决问题的能力。同时，通过直接对顺序栈的各种操作，加深了对数据结构的理解和认识。并在完成课程设计的过程作主动查阅了相关资料，学到了不少课本上没有的技术知识。在整个设计过程中，构思是很花费时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多也时用错了方法，总是实现不了。同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。希望可以通过以后的学习不断进步。

[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2021.

部分思路借鉴算术表达式求值（C语言栈）_夜何其的博客-CSDN博客_c语言利用栈求解算术表达式侵删致歉