[中缀表达式转后缀表达式并求值-C语言] - 1
中缀表达式转后缀表达式(逆波兰式)并求值的C语言实现
前言
学习C语言之初利用switch-case制作简易计算器时就想过如何计算复杂算式,大一结束有了一定数据结构与算法知识,决定实现此功能。
整体说明
C语言库
使用了 io 和 lib 两个标准C语言库
<stdio.h> <stdlib.h>
数据结构
构建了三个数据结构
List / LList / ComList
使用算法
大量使用递归,部分宏定义,特殊数据结构全部使用堆内存
数据结构
List
用来盛放字符型数字或表达式(长度没有限制)
内置属性
1 | char val; // 用来盛放字符,解析输入的字符串时使用 |
pushNewList
将一个字符加入链表的末尾,并返回一个指针指向该链表的头结点
参数:
char: 要加入的字符
List*:指向链表的头结点,若为空指针则会创建一个新链表
返回:
List*:链表头节点
getLastListVal
返回一个链表末尾节点的值
参数:
List*:指向链表头节点,若为空指针则返回 ‘ a ’
返回:
char:获得的字符
clearLastList
去除链表末尾节点并释放内存,返回一个指针指向该链表的头结点;
若用于仅有一个节点的链表,则返回空指针
参数:
List*:指向链表头节点,若为空指针则返回空指针
返回:
List*:指向链表头节点
getListLength
获取链表的长度
参数:
List*:指向链表头节点,若为空指针则返回 0
返回:
int:链表长度
LList
同来盛放中缀表达式或后缀表达式
内置属性
1 | int isMinus; //记录数字是否为负数 |
方法
同List , 但是没有 getListLength 方法
ComList
用来临时盛放计算时的数字(用作栈)
内置属性
1 | double val;//盛放数字 |
方法
同List 和 LList , 也没有 getListLength 方法
主要逻辑
思路
第一步:接收字符串后将其转化存入LList中,作为中缀表达式;
第二步:将中缀表达式转化为后缀表达式;
第三步:计算后缀表达式的值;
我们根据思路,可以声明三个子函数:
1 | LList* strToLList(char* s,int start,LList* this); |
具体函数实现细节将发布于其他文章 @taiga-a.github.io
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Taiga_A!
评论