中缀表达式转后缀表达式（逆波兰式）并求值的C语言实现

前言

学习C语言之初利用switch-case制作简易计算器时就想过如何计算复杂算式，大一结束有了一定数据结构与算法知识，决定实现此功能。

整体说明

C语言库

使用了 io 和 lib 两个标准C语言库

<stdio.h> <stdlib.h>

数据结构

构建了三个数据结构

List / LList / ComList

使用算法

大量使用递归，部分宏定义，特殊数据结构全部使用堆内存

数据结构

List

用来盛放字符型数字或表达式（长度没有限制）

内置属性
1
2
char val; // 用来盛放字符，解析输入的字符串时使用
List* next; //指向下一个节点
pushNewList

将一个字符加入链表的末尾，并返回一个指针指向该链表的头结点

参数：

​ char： 要加入的字符

​ List*：指向链表的头结点，若为空指针则会创建一个新链表

返回：

​ List*：链表头节点

getLastListVal

返回一个链表末尾节点的值

参数：

​ List*：指向链表头节点，若为空指针则返回 ‘ a ’

返回：

​ char：获得的字符

clearLastList

去除链表末尾节点并释放内存，返回一个指针指向该链表的头结点；

若用于仅有一个节点的链表，则返回空指针

参数：

​ List*：指向链表头节点，若为空指针则返回空指针

返回：

​ List*：指向链表头节点

getListLength

获取链表的长度

参数：

​ List*：指向链表头节点，若为空指针则返回 0

返回：

​ int：链表长度

LList

同来盛放中缀表达式或后缀表达式

内置属性
1
2
3
int isMinus; //记录数字是否为负数
List* valList; //链表，盛放多位数字 或 计算符号
LList* next;//指向下一节点
方法

同List , 但是没有 getListLength 方法

ComList

用来临时盛放计算时的数字（用作栈）

内置属性
1
2
double val;//盛放数字
comList* next;//指向下一节点
方法

同List 和 LList , 也没有 getListLength 方法

主要逻辑

思路

第一步：接收字符串后将其转化存入LList中，作为中缀表达式；

第二步：将中缀表达式转化为后缀表达式；

第三步：计算后缀表达式的值；

我们根据思路，可以声明三个子函数：

1
2
3
LList* strToLList(char* s,int start,LList* this);
LList* midToRPN(LList* mid,List* pop,int isR);
double computeRPN(LList* rpn, comList* pop);

具体函数实现细节将发布于其他文章 @taiga-a.github.io

本文附属源码 - Github