【数据结构--栈】c语言实现计算器|后缀表达式|栈的操作

这个计算器不是包含了所有可能遇到的情况，因为学业紧张，所以bug没有改，但是可以实现加减乘除运算和括号的优先级判断。 以后有机会可能会把bug改过来。 小数的运算（有优先级判断）：

---

对于计算器来说，复杂的符号优先级判断是通过栈来完成的。

我们把输入的计算式叫做中缀表达式，比如：

3+5*（4-6）

我们要把他换成后缀表达式：

从左到右遍历中缀表达式的每一个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

--》》》 3546-*+

计算后缀表达式：

从左到右遍历后缀表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈。

--》》》栈：3

--》》》栈：35

--》》》栈：354

--》》》栈：3546

--》》》栈：35-2

--》》》栈：3-10

--》》》栈：-7

---

在c语言里面，我们可以设置两个栈，一个数据栈，一个符号栈，数据栈用来表示数字的运算情况，符号栈用来表示符号的运算情况。

那么以上结果的生成可细分为以下步骤：

---》》》数据栈：3  符号栈：null

---》》》数据栈： 3   符号栈：+

---》》》数据栈：35   符号栈：+

---》》》数据栈： 35  符号栈：+*

---》》》数据栈：35    符号栈： +*（

---》》》数据栈：354    符号栈： +*（

---》》》数据栈：354  符号栈： +*（-

---》》》数据栈：3546  符号栈： +*（-）

---》》》数据栈：35-2   符号栈： +*

---》》》数据栈：3-10    符号栈： +

---》》》数据栈：-7    符号栈：null

---

代码实现的时候注意一下可能会出现的所有情况即可。

以下是我的代码（有点bug，仅供参考和交流）：

头文件：head.h

#pragma once#include #include #include #include #define MAXSIZE 50//数据栈struct Data{double num[MAXSIZE];int top;};//符号栈struct Sign{char s[MAXSIZE];int top;};//数据栈置空void init_data(struct Data* data){data->top = -1;}//符号栈置空void init_sign(struct Sign* sign){sign->top = -1;}//数据栈满int judge_data_max(struct Data* data){if (data->top == MAXSIZE - 1){printf("数据栈已经满了哦");return 0;}return 1;}//符号栈满int judge_sign_max(struct Sign* sign){if (sign->top == MAXSIZE - 1){printf("符号栈已经满了哦");return 0;}return 1;}//数据栈判空int judge_data_zero(struct Data* data){if (data->top == -1){//printf("数据栈已经空了哦");return 0;}return 1;}//符号栈判空int judge_sign_zero(struct Sign* sign){if (sign->top == -1){//printf("符号栈已经空了哦");return 0;}return 1;}//数据栈入栈void create_data(struct Data* data, double num){ int judge = judge_data_max(data);if (judge == 1){data->top++;data->num[data->top] = num;}}//符号栈入栈void create_sign(struct Sign* sign, char s){int judge = judge_sign_max(sign);if (judge == 1){sign->top++;sign->s[sign->top] = s;}}//数据栈出栈double data_out(struct Data* data){int judge = judge_data_zero(data);double num;if (judge == 1){num = data->num[data->top];data->top--;}return num;}//符号栈出栈char sign_out(struct Sign* sign){int judge = judge_sign_zero(sign);char s = (char)malloc(sizeof(char));if (judge == 1){s = sign->s[sign->top];sign->top--;}return s;}//读取数据栈double read_data(struct Data* data){return data->num[data->top];}//读取符号栈char read_sign(struct Sign* sign){return sign->s[sign->top];}//四则运算double math(double x, double y, char s){switch (s){case '+':return x + y;case '-':return x - y;case '/':return x / y;case '*':default:return x * y;}}//优先级判断int judge(char s){switch (s){case '(':return 1;case '+':case '-':return 2;case '*':case '/':return 3;case ')':return 4;}}

源文件：demo.c

#include "head.h"//输入中缀表达式void input(char* before_list){char ch;int index = 0;printf("输入'='(等于)计算结果！不要输入回车。。n");while ((ch = getch())){if (ch == '='){break;}before_list[index++] = ch;printf("%c", ch);}before_list[index] = '';}//对每一次的符号栈改变进行计算，直到循环结束void in_out(struct Data* data, struct Sign* sign){if (sign->top == 0){return;}char ch = sign_out(sign);char ch2;if (ch == ')'){while ((ch2 = sign_out(sign)) != '('){double num1 = data_out(data), num2 = data_out(data);double num = math(num2, num1, ch2);create_data(data, num);}}else{while (judge(read_sign(sign)) >= judge(ch)){ch2 = sign_out(sign);double num1 = data_out(data), num2 = data_out(data);double num = math(num2, num1, ch2);create_data(data, num);}create_sign(sign, ch);}}//清空符号栈void clean_sign(struct Data* data, struct Sign* sign){char ch;while (judge_sign_zero(sign)){ch = sign_out(sign);double num1 = data_out(data), num2 = data_out(data);double num = math(num2, num1, ch);create_data(data, num);}}//输出结果void show_answer(struct Data* data){double answer = data_out(data);printf("n%.2lf", answer);}void run(){//数据栈struct Data* data = (struct Data*)malloc(sizeof(struct Data));init_data(data);//符号栈struct Sign* sign = (struct Sign*)malloc(sizeof(struct Sign));init_sign(sign);//前缀表达式char* before_list = (char*)malloc(sizeof(char) * MAXSIZE);//保存每一个数字char* nums_list = (char*)malloc(sizeof(char) * MAXSIZE);//生成前缀表达式input(before_list);//计算int before_index, num_index, target;before_index = num_index = target = 0;for (; before_list[before_index] != ''; before_index++){if (before_list[before_index] >= '0' && before_list[before_index] <= '9' || before_list[before_index] == '.'){nums_list[num_index++] = before_list[before_index];target = 1;if (before_list[before_index + 1] == ''){nums_list[num_index] = '';create_data(data, atof(nums_list));num_index = 0;}}else{if (target == 1 || before_list[before_index] == ')'){nums_list[num_index] = '';create_data(data, atof(nums_list));num_index = 0;create_sign(sign, before_list[before_index]);in_out(data, sign);target = 0;}else{create_sign(sign, before_list[before_index]);}}}clean_sign(data, sign);//输出结果show_answer(data);}

int main(){while (1){run();fflush(stdin);system("pause");system("clear");}}

---

欢迎大家交流讨论！！！