利用堆栈计算表达式c语言

时间: 2023-08-25 19:38:11 浏览: 54
可以使用堆栈来计算中缀表达式,具体步骤如下: 1. 定义一个操作数栈和一个操作符栈。 2. 从左到右扫描表达式,如果遇到操作数,则压入操作数栈。 3. 如果遇到操作符,将其与操作符栈栈顶元素进行比较: - 如果操作符栈为空,或者栈顶操作符为左括号,则直接将此操作符入栈。 - 否则,若优先级比栈顶操作符优先级高,则将此操作符入栈。 - 否则,将操作符栈栈顶元素弹出并压入操作数栈中,再次转到3.1与新的栈顶操作符比较。 4. 如果遇到左括号,则直接压入操作符栈。 5. 如果遇到右括号,则执行出栈操作,直到遇到左括号为止,将这一对括号丢弃。 6. 重复步骤2至5,直到表达式的最右边。 7. 最后将操作符栈中剩余的操作符依次弹出并压入操作数栈中。 8. 操作数栈顶元素即为表达式的结果。 下面是一个使用堆栈计算表达式的C语言代码示例: ```c #include <stdio.h> #include <stdlib.h> #include <ctype.h> typedef struct stack { int top; int* data; } Stack; Stack* createStack(int size) { Stack* s = (Stack*)malloc(sizeof(Stack)); s->top = -1; s->data = (int*)malloc(size * sizeof(int)); return s; } void push(Stack* s, int value) { s->data[++s->top] = value; } int pop(Stack* s) { return s->data[s->top--]; } int peek(Stack* s) { return s->data[s->top]; } int isEmpty(Stack* s) { return s->top == -1; } int priority(char op) { if (op == '+' || op == '-') { return 1; } else if (op == '*' || op == '/') { return 2; } else { return 0; } } int evaluate(char* expression) { Stack* numStack = createStack(100); Stack* opStack = createStack(100); int i = 0; while (expression[i] != '\0') { if (isdigit(expression[i])) { int num = 0; while (isdigit(expression[i])) { num = num * 10 + (expression[i] - '0'); i++; } push(numStack, num); } else if (expression[i] == '(') { push(opStack, expression[i]); i++; } else if (expression[i] == ')') { while (peek(opStack) != '(') { int num2 = pop(numStack); int num1 = pop(numStack); char op = pop(opStack); if (op == '+') { push(numStack, num1 + num2); } else if (op == '-') { push(numStack, num1 - num2); } else if (op == '*') { push(numStack, num1 * num2); } else if (op == '/') { push(numStack, num1 / num2); } } pop(opStack); i++; } else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/') { while (!isEmpty(opStack) && priority(peek(opStack)) >= priority(expression[i])) { int num2 = pop(numStack); int num1 = pop(numStack); char op = pop(opStack); if (op == '+') { push(numStack, num1 + num2); } else if (op == '-') { push(numStack, num1 - num2); } else if (op == '*') { push(numStack, num1 * num2); } else if (op == '/') { push(numStack, num1 / num2); } } push(opStack, expression[i]); i++; } else { i++; } } while (!isEmpty(opStack)) { int num2 = pop(numStack); int num1 = pop(numStack); char op = pop(opStack); if (op == '+') { push(numStack, num1 + num2); } else if (op == '-') { push(numStack, num1 - num2); } else if (op == '*') { push(numStack, num1 * num2); } else if (op == '/') { push(numStack, num1 / num2); } } int result = pop(numStack); free(numStack->data); free(numStack); free(opStack->data); free(opStack); return result; } int main() { char expression[] = "1+2*3-(4+5)/6"; printf("%s = %d\n", expression, evaluate(expression)); return 0; } ```

相关推荐

最新推荐

recommend-type

基于堆栈的后缀表达式的生成与计算

基于堆栈的后缀表达式的生成与计算 存储结构实现有链式存储结构和线性存储结构。 本人在此试验中是用链式存储结构编写的。
recommend-type

Golang捕获panic堆栈信息的讲解

今天小编就为大家分享一篇关于Golang捕获panic堆栈信息的讲解,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
recommend-type

Android activity堆栈及管理实例详解

主要介绍了Android activity堆栈及管理实例详解的相关资料,非常不错,具有参考借鉴价值,对android activity堆栈相关知识感兴趣的朋友一起学习吧
recommend-type

Java如何自定义异常打印非堆栈信息详解

主要给大家介绍了关于Java如何自定义异常打印非堆栈信息的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧。
recommend-type

c语言难点分析整理,C语言

53. 算术表达式的计算 265 54. 结构体对齐的具体含义 269 55. 连连看AI算法 274 56. 连连看寻路算法的思路 283 57. 重新认识:指向函数的指针 288 58. 链表的源码 291 59. 高质量的子程序 295 60. 高级C语言程序员...
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

【实战演练】MATLAB用遗传算法改进粒子群GA-PSO算法

![MATLAB智能算法合集](https://static.fuxi.netease.com/fuxi-official/web/20221101/83f465753fd49c41536a5640367d4340.jpg) # 2.1 遗传算法的原理和实现 遗传算法(GA)是一种受生物进化过程启发的优化算法。它通过模拟自然选择和遗传机制来搜索最优解。 **2.1.1 遗传算法的编码和解码** 编码是将问题空间中的解表示为二进制字符串或其他数据结构的过程。解码是将编码的解转换为问题空间中的实际解的过程。常见的编码方法包括二进制编码、实数编码和树形编码。 **2.1.2 遗传算法的交叉和
recommend-type

openstack的20种接口有哪些

以下是OpenStack的20种API接口: 1. Identity (Keystone) API 2. Compute (Nova) API 3. Networking (Neutron) API 4. Block Storage (Cinder) API 5. Object Storage (Swift) API 6. Image (Glance) API 7. Telemetry (Ceilometer) API 8. Orchestration (Heat) API 9. Database (Trove) API 10. Bare Metal (Ironic) API 11. DNS
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。