中缀表达式转后缀表达式(逆波兰式)并求值的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