利用顺序栈完成表达式求值（将字符型转换为整型）
程序代码：
| #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <math.h> #define MAXSIZE 100 #define ElemType char #define LEN sizeof(ElemType) typedef struct{ ElemType* data; int top; }SqStack; void InitStack(SqStack* S) { S->data = (ElemType*)malloc(MAXSIZE * LEN); if (S->data == NULL) exit(0); S->top = 0; } int StackEmpty(SqStack* S) { if (S->top == 0) return 1; else return 0; } int StackFull(SqStack* S) { if (S->top == MAXSIZE) return 1; else return 0; } int Push(SqStack* S, ElemType x) { if (StackFull(S)) return 0; S->data[S->top] = x; (S->top)++; return 1; } ElemType Pop(SqStack* S) { ElemType x; if (StackEmpty(S)) return 0; --(S->top); x = S->data[S->top]; return x; } ElemType GetTop(SqStack* S) { ElemType x; if (StackEmpty(S)) return 0; x = S->data[(S->top) - 1]; return x; } int IfOptr(char c) { switch (c) { case '+': case '-': case '*': case '/': case '(': case ')': case '#':return 1; default:return 0; } } char Operate(ElemType a_c, ElemType op, ElemType b_c) { int a = a_c - '0'; int b = b_c - '0'; switch (op) { case '+': {int x = a + b; return (x + 48); } case '-': {int x = a - b; return (x + 48); } case '*': {int x = a * b; return (x + 48); } case '/': {int x = a / b; return (x + 48); } default:exit(1); } } char Precede(char c1, char c2) { int c_temp1,c_temp2; switch (c1) { case '*': case '/':c_temp1 = 4; break; case '+': case '-':c_temp1 = 2; break; case '(':c_temp1 = 0; break; case ')':c_temp1 = 5; break; case '#':c_temp1 = -1; } switch (c2) { case '*': case '/': c_temp2 = 3; break; case '+': case '-': c_temp2 = 1; break; case '(': c_temp2 = 5; break; case ')': c_temp2 = 0; break; case '#': c_temp2 = -1; } if (c_temp1<c_temp2) return('<'); else if(c_temp1==c_temp2) return('='); else return('>'); } int main() { SqStack* OPTR= (SqStack*)malloc(sizeof(SqStack)); SqStack* OPND= (SqStack*)malloc(sizeof(SqStack)); char c; InitStack(OPTR); Push(OPTR, '#'); InitStack(OPND); c = getchar(); while (c != '#' || GetTop(OPTR) != '#') { if (!IfOptr(c)) { Push(OPND, c); c = getchar(); } else switch (Precede(GetTop(OPTR),c)) { case '<': Push(OPTR, c); c = getchar(); break; case '=': { ElemType x = Pop(OPTR); c = getchar(); break; } case '>': { ElemType op = Pop(OPTR); ElemType b = Pop(OPND); ElemType a = Pop(OPND); Push(OPND,Operate(a, op, b)); break; } } } printf("%c",GetTop(OPND)); } |
运行截图：
利用顺序栈完成表达式求值（创建字符型、整型两种栈）
程序代码：
SqStackInt.h
| #include <stdio.h> #include <malloc.h> #include <stdlib.h> #define MAXSIZE 100 typedef struct { int* data; int top; }SqStackInt; void InitStack_Int(SqStackInt* S) { S->data = (int*)malloc(MAXSIZE * sizeof(int)); if (S->data == NULL) exit(0); S->top = 0; } int StackEmpty_Int(SqStackInt* S) { if (S->top == 0) return 1; else return 0; } int StackFull_Int(SqStackInt* S) { if (S->top == MAXSIZE) return 1; else return 0; } int Push_Int(SqStackInt* S, int x) { if (StackFull_Int(S)) return 0; S->data[S->top] = x; (S->top)++; return 1; } int Pop_Int(SqStackInt* S) { int x; if (StackEmpty_Int(S)) return 0; --(S->top); x = S->data[S->top]; return x; } int GetTop_Int(SqStackInt* S) { int x; if (StackEmpty_Int(S)) return 0; x = S->data[(S->top) - 1]; return x; } |
SqStackChar.h
| #include <stdio.h> #include <malloc.h> #include <stdlib.h> #define MAXSIZE 100 typedef struct { char* data; int top; }SqStackChar; void InitStack_Char(SqStackChar* S) { S->data = (char*)malloc(MAXSIZE * sizeof(char)); if (S->data == NULL) exit(0); S->top = 0; } int StackEmpty_Char(SqStackChar* S) { if (S->top == 0) return 1; else return 0; } int StackFull_Char(SqStackChar* S) { if (S->top == MAXSIZE) return 1; else return 0; } int Push_Char(SqStackChar* S, char x) { if (StackFull_Char(S)) return 0; S->data[S->top] = x; (S->top)++; return 1; } char Pop_Char(SqStackChar* S) { char x; if (StackEmpty_Char(S)) return 0; --(S->top); x = S->data[S->top]; return x; } char GetTop_Char(SqStackChar* S) { char x; if (StackEmpty_Char(S)) return 0; x = S->data[(S->top) - 1]; return x; } |
Main.cpp
| #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include "SqStackChar.h" #include "SqStackInt.h" int IfOptr(char c) { switch (c) { case '+': case '-': case '*': case '/': case '(': case ')': case '#':return 1; default:return 0; } } char Operate( int a, char op, int b) { switch (op) { case '+': return (a + b); case '-': return (a - b); case '*': return (a * b); case '/': return (a / b); default:exit(1); } } char Precede(char c1, char c2) { int c_temp1, c_temp2; switch (c1) { case '*': case '/':c_temp1 = 4; break; case '+': case '-':c_temp1 = 2; break; case '(':c_temp1 = 0; break; case ')':c_temp1 = 5; break; case '#':c_temp1 = -1; } switch (c2) { case '*': case '/': c_temp2 = 3; break; case '+': case '-': c_temp2 = 1; break; case '(': c_temp2 = 5; break; case ')': c_temp2 = 0; break; case '#': c_temp2 = -1; } if (c_temp1 < c_temp2) return('<'); else if (c_temp1 == c_temp2) return('='); else return('>'); } int main() { SqStackChar* OPTR = (SqStackChar*)malloc(sizeof(SqStackChar)); SqStackInt* OPND = (SqStackInt*)malloc(sizeof(SqStackInt)); char c; InitStack_Char(OPTR); Push_Char(OPTR, '#'); InitStack_Int(OPND); c = getchar(); while (c != '#' || GetTop_Char(OPTR) != '#') { if (!IfOptr(c)) { int n = c - '0'; Push_Int(OPND, n); c = getchar(); } else switch (Precede(GetTop_Char(OPTR), c)) { case '<': Push_Char(OPTR, c); c = getchar(); break; case '=': { char x = Pop_Char(OPTR); c = getchar(); break; } case '>': { char op = Pop_Char(OPTR); int b = Pop_Int(OPND); int a = Pop_Int(OPND); Push_Int(OPND, Operate(a, op, b)); break; } } } printf("%d", GetTop_Int(OPND)); } |
运行截图：
利用链栈完成表达式求值（创建字符型、整型两种栈）
程序代码：
LinkStackInt.h
| #include<stdio.h> #include<stdlib.h> #include<malloc.h> typedef struct StackNodeInt { int data; struct StackNodeInt* link; }StackNodeInt; StackNodeInt* InitStack_Int() { StackNodeInt* top = (StackNodeInt*)malloc(sizeof(StackNodeInt)); if (top == NULL) { printf("动态空间分配失败！"); exit(-1); } top->link = NULL; return(top); } int StackEmpty_Int(StackNodeInt* top) { if (top->link == NULL) return 1; else return 0; } void Push_Int(StackNodeInt* top, int x) { StackNodeInt* p = (StackNodeInt*)malloc(sizeof(StackNodeInt)); if (p == NULL) { printf("动态空间分配失败！"); exit(-1); } p->link = top->link; p->data = x; top->link = p; } int Pop_Int(StackNodeInt* top) { if (StackEmpty_Int(top)) { exit(-1); } StackNodeInt* p; p = top->link; int x = p->data; top->link = p->link; free(p); return x; } int GetTop_Int(StackNodeInt* top) { if (StackEmpty_Int(top)) { return 0; } int x = top->link->data; return x; } |
LinkStackChar.h
| #include<stdio.h> #include<stdlib.h> #include<malloc.h> typedef struct StackNodeChar { char data; struct StackNodeChar* link; }StackNodeChar; StackNodeChar* InitStack_Char() { StackNodeChar* top= (StackNodeChar*)malloc(sizeof(StackNodeChar)); if (top == NULL) { printf("动态空间分配失败！"); exit(-1); } top->link = NULL; return(top); } int StackEmpty_Char(StackNodeChar* top) { if (top->link == NULL) return 1; else return 0; } void Push_Char(StackNodeChar* top,char x) { StackNodeChar* p = (StackNodeChar*)malloc(sizeof(StackNodeChar)); if (p == NULL) { printf("动态空间分配失败！"); exit(-1); } p->link = top->link; p->data = x; top->link = p; } char Pop_Char(StackNodeChar* top) { if (StackEmpty_Char(top)) { exit(-1); } StackNodeChar* p; p = top->link; char x = p->data; top->link = p->link; free(p); return x; } char GetTop_Char(StackNodeChar* top) { if (StackEmpty_Char(top)) { return 0; } char x = top->link->data; return x; } |
Main.cpp
| #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include "LinkStackChar.h" #include "LinkStackInt.h" int IfOptr(char c) { switch (c) { case '+': case '-': case '*': case '/': case '(': case ')': case '#':return 1; default:return 0; } } char Operate(int a, char op, int b) { switch (op) { case '+': return (a + b); case '-': return (a - b); case '*': return (a * b); case '/': return (a / b); default:exit(1); } } char Precede(char c1, char c2) { int c_temp1, c_temp2; switch (c1) { case '*': case '/':c_temp1 = 4; break; case '+': case '-':c_temp1 = 2; break; case '(':c_temp1 = 0; break; case ')':c_temp1 = 5; break; case '#':c_temp1 = -1; } switch (c2) { case '*': case '/': c_temp2 = 3; break; case '+': case '-': c_temp2 = 1; break; case '(': c_temp2 = 5; break; case ')': c_temp2 = 0; break; case '#': c_temp2 = -1; } if (c_temp1 < c_temp2) return('<'); else if (c_temp1 == c_temp2) return('='); else return('>'); } int main() { char c; StackNodeChar* OPTR = InitStack_Char(); Push_Char(OPTR, '#'); StackNodeInt* OPND=InitStack_Int(); c = getchar(); while (c != '#' || GetTop_Char(OPTR) != '#') { if (!IfOptr(c)) { int n = c - '0'; Push_Int(OPND, n); c = getchar(); } else switch (Precede(GetTop_Char(OPTR), c)) { case '<': Push_Char(OPTR, c); c = getchar(); break; case '=': { char x = Pop_Char(OPTR); c = getchar(); break; } case '>': { char op = Pop_Char(OPTR); int b = Pop_Int(OPND); int a = Pop_Int(OPND); Push_Int(OPND, Operate(a, op, b)); break; } } } printf("%d", GetTop_Int(OPND)); } |
运行截图：
实验小结
① 了解掌握整型数据与字符型的转化规则
在“利用顺序栈完成表达式求值（将字符型转换为整型）”实验中，因为我只创建了字符栈，所以只能将数据作为字符存放在字符栈中，而作为字符型数据存储的数字不能计算出正确结果，所以必须在计算前，将作为字符存放的数字转换为整型数据。那如何转换呢？举个例子： ‘1’的ASCII 值为 49；‘0’的ASCII 值为 48；‘1’-‘0’=1；‘0’是一个char类型的字符，其ASCII码就是一个int型的数字48，在运算过程中等同于int。所以将字符型数字‘1’转化为 整型数字1：‘1’-‘0’=1相当于49-48 = 1。
② 时刻警惕“野指针”
在程序编写完成后，调试过程中却不断报错：“C4700：使用了未初始化的局部变量‘OPTR’和‘OPRD’”，在查阅资料并多番询问后。最终找出错误：缺少如下代码：
SqStack* OPTR = (SqStack*)malloc(sizeof(SqStack));
SqStack* OPND = (SqStack*)malloc(sizeof(SqStack));
换言之，我在初始化OPTR和OPND两个顺序栈的指针时，没有给指针分配地址空间，而让他们成为“野指针”。我一直存在一个思维误区：我需要开辟空间给栈存放数据，并将栈的地址返回给它的指针，也就是OPTR和OPTD。存放数据固然要开辟空间，但是存放这些数据的地址也同样要开辟空间。我就是因为没有给栈的地址开辟空间存放而报错。之后的编程，要时刻警惕野指针的存在。
③ 自定义头文件文章来源：https://www.toymoban.com/news/detail-745519.html
如果在一个文件中，写上成百上千行的代码，这些代码阅读起来就会很麻烦。因此，我们可以引入头文件，把自己写的函数放入头文件中，然后直接调用到主程序中，这样在主程序中看起来就比较清晰。本次实验，我将栈的定义及其相关操作单独放在一个头文件中，并在主程序的头部调用，这样主程序就只剩下与计算相关的函数，整个程序脉络更为清晰，可读性更高。文章来源地址https://www.toymoban.com/news/detail-745519.html
到了这里，关于【数据结构】利用顺序栈/链栈完成表达式求值（C语言实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
