链栈
公共Code
typedef struct StackNode{
int data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct{
LinkStackPtr top;
int count;
} LinkStack;
void linkStackTestMethod(void);
//链栈的初始化
int initWithStack(LinkStack *linkStack){
linkStack->top = (LinkStackPtr)malloc(sizeof(StackNode));
if (!linkStack->top) {
return FALSE;
}
linkStack->top = NULL;
linkStack->count = 0;
return TRUE;
}
//判断栈是否为空
int isLinkStackEmpty(LinkStack *linkStack){
if (linkStack->count > 0) {
return TRUE;
}else {
return FALSE;
}
}
//栈元素遍历
int linkStackTraverse(LinkStack linkStack){
if (linkStack.count > 0) {
StackNode *node = linkStack.top;
while (node) {
printf(" %d,", node->data);
node = node->next;
}
}else {
return FALSE;
}
printf("\n\n");
return TRUE;
}
进栈
链栈 push
//栈的push
int pushInStack(LinkStack *linkStack, int data){
StackNode *insertNode = (StackNode *)malloc(sizeof(StackNode));
insertNode->data = data;
//把当前的栈顶元素赋值给新结点的直接后继，见图中①
insertNode->next = linkStack->top;
//将新的结点s赋值给栈顶指针，见图中②
linkStack->top = insertNode;
linkStack->count ++;
return TRUE;
}
void linkStackTestMethod(void){
LinkStack linkStack;
int statusCode = initWithStack(&linkStack);
if (statusCode) {
for (int i = 0; i <11; i ++) {
pushInStack(&linkStack, i);
}
}
linkStackTraverse(linkStack);
}
输出：
10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
出栈
链栈出栈
//栈的pop
int pushOutStack(LinkStack *linkStack,int *data){
//将栈顶结点赋值给p，见图中③
StackNode *outNode = linkStack->top;
*data = outNode->data; //不能是data = &(outNode->data),这是把它的地址值赋给data
//使得栈顶指针下移一位，指向后一结点，见图中④
linkStack->top = outNode->next;
//释放结点p
free(outNode);
linkStack->count--;
return TRUE;
}
void linkStackTestMethod(void){
LinkStack linkStack;
int statusCode = initWithStack(&linkStack);
if (statusCode) {
for (int i = 0; i <11; i ++) {
pushInStack(&linkStack, i);
}
}
int popE;
pushOutStack(&linkStack, &popE);
printf("出栈的元素popE是：%d\n\n",popE);
linkStackTraverse(linkStack);
}
输出：
出栈的元素popE是：10
9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
清空栈元素
//清空栈
int clearLinkStack(LinkStack *linkStack){
if (linkStack->count == 0) {
return FALSE;
}
StackNode *deleteNode = linkStack->top;
while (deleteNode) {
linkStack->top = deleteNode->next;
free(deleteNode);
deleteNode = linkStack->top;
}
linkStack->count = 0;
return TRUE;
}
void linkStackTestMethod(void){
LinkStack linkStack;
int statusCode = initWithStack(&linkStack);
if (statusCode) {
for (int i = 0; i <11; i ++) {
pushInStack(&linkStack, i);
}
}
statusCode = clearLinkStack(&linkStack);
linkStackTraverse(linkStack);
printf("清空栈后，栈空否：%d(1:空 0:否)", statusCode);
printf("\n\n");
}
输出：
清空栈后，栈空否：1(1:空 0:否)
栈的应用 -- 四则运算表达式
中缀表达式：9+(3-1)x3+10÷2
后缀表达式：9 3 1 - 3 x + 10 2 ÷ +
后缀表达式规则：
从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
后缀表达式计算:
将后缀表达式从左到右依次遍历，如果当前元素为数字则入（操作数）栈，如果为操作符，则pop出栈顶两个元素（第一次pop出的是右操作数，第二次pop出的是左操作数）进行运算，然后将计算结果再次入栈，直至表达式结束，此时操作数栈内理应只剩一个元素即表达式结果。
中缀转后缀规则：
①. 从左到右遍历中缀表达式中的每个数字和符号；
②. 若是数字就输出，即成为后缀表达式的一部分；
③. 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
中缀转后缀详细过程：
①. 遍历中缀表达式；
②. 如果当前中缀元素为操作数，则直接将此操作数“输出”到后缀表达式尾端；
③. 如果当前中缀元素为'*'，'/'或'('，直接push入操作符栈；
④. 如果当前中缀元素为')'，则依次pop出栈顶操作符，“输出”到后缀表达式尾端，直至pop得到的是一个'('才停止，并丢弃该'('；
⑤. 如果当前中缀元素为'+'或'-'，则依次pop出栈顶操作符、“输出”到后缀表达式尾端，直至栈底（栈空）或pop得到了一个'('，若pop得到一个'('，将'('重新push入栈。达到这两个条件之一后，将此操作符（'+'或'-'）入栈；
⑥. 如果当前中缀元素为'='，则依次pop出栈顶操作符、“输出”到后缀表达式尾端，直至栈底（栈空）。
注意：根据④、⑤两点，可以看出：只有遍历到')'才会导致'('弹出，其它操作符均不会使'('弹出。
完整Code
Arithmetic.h 文件
#ifndef Arithmetic_h
#define Arithmetic_h
#include <stdio.h>
#include <stdlib.h>
#include "LinearListStoragge.h"
typedef struct OperationNode{
char operation;
struct OperationNode *next;
} OperationNode;
typedef struct {
struct OperationNode *top;
int count;
} OperationStack;
typedef struct CharacterNode{
char number;
struct CharacterNode *next;
} CharacterNode;
//后缀表达式栈
typedef struct {
struct CharacterNode *top;
int count;
} PostfixStack;
void arithmeticCalculateTest(void);
#endif /* Arithmetic_h */
Arithmetic.c 文件
//
// Arithmetic.c
// DataStructure
//
// Created by Harley on 2019/4/17.
// Copyright © 2019 Harley'sMac. All rights reserved.
//
#include "Arithmetic.h"
#include <string.h>
//前缀表达式字符数组
char PrefixCharacter[100];
//操作符栈初始化
int initWithOperationStack(OperationStack *operataionStack){
operataionStack->top = (OperationNode *)malloc(sizeof(OperationNode));
if (!operataionStack->top) {
return FALSE;
}
operataionStack->top = NULL;
operataionStack->count = 0;
return TRUE;
}
//后缀表达式栈初始化
int initWithPostfixStack(PostfixStack *postfixStack){
postfixStack->top = (CharacterNode *)malloc(sizeof(CharacterNode));
if (!postfixStack->top) {
return FALSE;
}
postfixStack->top = NULL;
postfixStack->count = 0;
return TRUE;
}
//操作数进栈
int pushOperand(PostfixStack *postfixStack, char character){
CharacterNode *insertNode = (CharacterNode *)malloc(sizeof(CharacterNode));
if (!insertNode) {
return FALSE;
}
insertNode->number = character;
insertNode->next = postfixStack->top;
postfixStack->top = insertNode;
postfixStack->count ++;
return TRUE;
}
//操作数出栈
int popOperand(PostfixStack *postfixStack, char *character){
CharacterNode *deleteNode = postfixStack->top;
*character = deleteNode->number;
postfixStack->top = deleteNode->next;
postfixStack->count--;
free(deleteNode);
return TRUE;
}
//操作符进栈
int pushOperator(OperationStack *operationStack, char character){
if (!character) {
return FALSE;
}
OperationNode *insertNode = (OperationNode *)malloc(sizeof(OperationNode));
insertNode->next = operationStack->top;
insertNode->operation = character;
operationStack->top = insertNode;
operationStack->count ++;
return TRUE;
}
//操作符出栈
int popOperator(OperationStack *operationStack, char *character){
OperationNode *deleteNode = operationStack->top;
if (deleteNode == NULL) {
return FALSE;
}
*character = deleteNode->operation;
operationStack->top = deleteNode->next;
operationStack->count --;
free(deleteNode);
return TRUE;
}
//对字符和数字进行存储
void judgeNumberOrCharacter(char character){
//判断为数字
// if (character >= '0' && character <= '9') {
// pushOperand(<#PostfixStack *postfixStack#>, <#char character#>)
// }
}
void traversePostfixStack(PostfixStack postfixStack){
printf("后缀表达式是：");
while (postfixStack.top != NULL) {
CharacterNode *node = postfixStack.top;
printf("%c ", node->number);
postfixStack.top = node->next;
}
printf("\n\n");
}
void traverseOperationStack(OperationStack operationStack){
printf("符号栈是：");
while (operationStack.top != NULL) {
OperationNode *node = operationStack.top;
printf("%c ", node->operation);
operationStack.top = node->next;
}
printf("\n\n");
}
//后缀表达式计算
int postfixExpressionCalculate(PostfixStack postfixStack){
CharacterNode *node = postfixStack.top;
if (node == NULL) {
return FALSE;
}
PostfixStack inverseOrder;
PostfixStack resultStack;
int statusDatus = initWithPostfixStack(&resultStack);
int statusCode = initWithPostfixStack(&inverseOrder);
printf("后缀表达式逆序%d(1 成功 0 失败)\n\n", statusCode);
while (postfixStack.top != NULL) {
char character = '\0';
popOperand(&postfixStack, &character);
pushOperand(&inverseOrder, character);
}
traversePostfixStack(inverseOrder);
//计算后缀表达式
while (inverseOrder.top != NULL) {
char character = '\0';
char leftNumber = '\0';
char rightNumber = '\0';
int result = 0;
popOperand(&inverseOrder, &character);
if (character >= '0' && character <= '9') {
pushOperand(&resultStack, character);
}else {
switch (character) {
case '+':{
popOperand(&resultStack, &rightNumber);
popOperand(&resultStack, &leftNumber);
leftNumber -= 48;
rightNumber -= 48;
result = rightNumber + leftNumber;
}
break;
case '-':{
popOperand(&resultStack, &rightNumber);
popOperand(&resultStack, &leftNumber);
leftNumber -= 48;
rightNumber -= 48;
result = leftNumber - rightNumber;
}
break;
case '*':{
popOperand(&resultStack, &rightNumber);
popOperand(&resultStack, &leftNumber);
leftNumber -= 48;
rightNumber -= 48;
result = leftNumber * rightNumber;
}
break;
case '/':{
popOperand(&resultStack, &rightNumber);
popOperand(&resultStack, &leftNumber);
leftNumber -= 48;
rightNumber -= 48;
result = leftNumber / rightNumber;
}
break;
default:
break;
}
//将计算的结果进行入栈,字符与数值相差48
pushOperand(&resultStack, (result +48));
printf("%d %c %d = %d \n", leftNumber, character, rightNumber, result);
}
}
char result = '\0';
popOperand(&resultStack, &result);
printf("结果值是：%d", (result -48));
return TRUE;
}
void arithmeticCalculateTest(void){
//状态码
int statusCode = 0;
//字符栈
OperationStack operationStack;
PostfixStack postfixStack;
statusCode = initWithOperationStack(&operationStack);
printf("操作符栈初始化成功%d(1是 0否)\n\n", statusCode);
statusCode = initWithPostfixStack(&postfixStack);
printf("后缀表达式栈初始化成功%d(1是 0否)\n\n", statusCode);
//字符串数组，C语言没有字符串，字符串使用字符组成的数组
char prefixCharacter[] = "9+(3-1)*3+8/2=";
printf("中缀表达式是：%s\n\n", prefixCharacter);
for (int i = 0; i< strlen(prefixCharacter); i++) {
traversePostfixStack(postfixStack);
traverseOperationStack(operationStack);
//判断为数字
if (prefixCharacter[i] >= '0' && prefixCharacter[i] <= '9') {
pushOperand(&postfixStack, prefixCharacter[i]);
}else {
printf("-->> %c\n", prefixCharacter[i]);
switch (prefixCharacter[i]) { //如果当前中缀元素为'+'或'-'，则依次pop出栈顶操作符、“输出”到后缀表达式尾端，直至栈底（栈空）或pop得到了一个'('，若pop得到一个'('，将'('重新push入栈。达到这两个条件之一后，将此操作符（'+'或'-'）入栈；
case '+':{
char character = '\0';
while (character != '(') {
popOperator(&operationStack, &character);
if (character != '(' && character != '\0') {
pushOperand(&postfixStack, character);
if (operationStack.top == NULL) {//出栈到栈顶，跳出循环将现在的'+'入栈
pushOperator(&operationStack, '+');
break;
}
}else {
pushOperator(&operationStack, character);
pushOperator(&operationStack, '+');
break;
}
}
}
break;
case '-':{
char character = '\0';
while (character != '(') {
popOperator(&operationStack, &character);
if (character != '(' && character != '\0') {
pushOperand(&postfixStack, character);
if (operationStack.top == NULL) {//出栈到栈顶，跳出循环将现在的'+'入栈
pushOperator(&operationStack, '-');
break;
}
}else {//遇到'('跳出循环
pushOperator(&operationStack, character);
pushOperator(&operationStack, '-');
break;
}
}
}
break;
case '*':{
pushOperator(&operationStack, '*');
}
break;
case '/':{
pushOperator(&operationStack, '/');
}
break;
case '(':{
pushOperator(&operationStack, '(');
}
break;
case ')':{ //如果当前中缀元素为')'，则依次pop出栈顶操作符，“输出”到后缀表达式尾端，直至pop得到的是一个'('才停止，并丢弃该'('
char character = '\0';
while (character != '(') {
popOperator(&operationStack, &character);
if (character != '(') {
pushOperand(&postfixStack, character);
}else{
break;
}
}
}
break;
case '=':{
char character = '\0';
while (operationStack.top != NULL) {
popOperator(&operationStack, &character);
pushOperand(&postfixStack, character);
}
}
break;
default:
break;
}
}
}
traversePostfixStack(postfixStack);
postfixExpressionCalculate(postfixStack);
}
输出打印：
操作符栈初始化成功1(1是 0否)
后缀表达式栈初始化成功1(1是 0否)
中缀表达式是：9+(3-1)*3+8/2=
后缀表达式是：
符号栈是：
后缀表达式是：9
符号栈是：
-->> +
后缀表达式是：9
符号栈是：+
-->> (
后缀表达式是：9
符号栈是：( +
后缀表达式是：3 9
符号栈是：( +
-->> -
后缀表达式是：3 9
符号栈是：- ( +
后缀表达式是：1 3 9
符号栈是：- ( +
-->> )
后缀表达式是：- 1 3 9
符号栈是：+
-->> *
后缀表达式是：- 1 3 9
符号栈是：* +
后缀表达式是：3 - 1 3 9
符号栈是：* +
-->> +
后缀表达式是：+ * 3 - 1 3 9
符号栈是：+
后缀表达式是：8 + * 3 - 1 3 9
符号栈是：+
-->> /
后缀表达式是：8 + * 3 - 1 3 9
符号栈是：/ +
后缀表达式是：2 8 + * 3 - 1 3 9
符号栈是：/ +
-->> =
后缀表达式是：+ / 2 8 + * 3 - 1 3 9
后缀表达式逆序1(1 成功 0 失败)
后缀表达式是：9 3 1 - 3 * + 8 2 / +
3 - 1 = 2
2 * 3 = 6
9 + 6 = 15
8 / 2 = 4
15 + 4 = 19
但是这个程序有一个问题，就是当操作数是大于10以上的数，计算会失误。这是因为当我把四则运算字符串分割成了一个数组，对于大于10的数，就分割为2位了，所以出错。若是，你有解决办法，请麻烦告知下，谢谢！
