【數(shù)據(jù)結(jié)構(gòu)】利用順序棧/鏈棧完成表達(dá)式求值（C語(yǔ)言實(shí)現(xiàn)）

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】利用順序棧/鏈棧完成表達(dá)式求值（C語(yǔ)言實(shí)現(xiàn)）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

利用順序棧完成表達(dá)式求值（將字符型轉(zhuǎn)換為整型）

程序代碼：

#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));

}

運(yùn)行截圖：

利用棧表達(dá)式求值c語(yǔ)言代碼,數(shù)據(jù)結(jié)構(gòu)基礎(chǔ),數(shù)據(jù)結(jié)構(gòu),c語(yǔ)言,算法

利用順序棧完成表達(dá)式求值（創(chuàng)建字符型、整型兩種棧）

程序代碼：

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));

}

運(yùn)行截圖：

利用棧表達(dá)式求值c語(yǔ)言代碼,數(shù)據(jù)結(jié)構(gòu)基礎(chǔ),數(shù)據(jù)結(jié)構(gòu),c語(yǔ)言,算法

利用鏈棧完成表達(dá)式求值（創(chuàng)建字符型、整型兩種棧）

程序代碼：

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("動(dòng)態(tài)空間分配失?。?);

???????? 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("動(dòng)態(tài)空間分配失?。?);

???????? 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("動(dòng)態(tài)空間分配失??！");

???????? 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("動(dòng)態(tài)空間分配失??！");

???????? 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));

}

運(yùn)行截圖：

利用棧表達(dá)式求值c語(yǔ)言代碼,數(shù)據(jù)結(jié)構(gòu)基礎(chǔ),數(shù)據(jù)結(jié)構(gòu),c語(yǔ)言,算法

實(shí)驗(yàn)小結(jié)

① 了解掌握整型數(shù)據(jù)與字符型的轉(zhuǎn)化規(guī)則

在“利用順序棧完成表達(dá)式求值（將字符型轉(zhuǎn)換為整型）”實(shí)驗(yàn)中，因?yàn)槲抑粍?chuàng)建了字符棧，所以只能將數(shù)據(jù)作為字符存放在字符棧中，而作為字符型數(shù)據(jù)存儲(chǔ)的數(shù)字不能計(jì)算出正確結(jié)果，所以必須在計(jì)算前，將作為字符存放的數(shù)字轉(zhuǎn)換為整型數(shù)據(jù)。那如何轉(zhuǎn)換呢？舉個(gè)例子： ‘1’的ASCII 值為 49；‘0’的ASCII 值為 48；‘1’-‘0’=1；‘0’是一個(gè)char類型的字符，其ASCII碼就是一個(gè)int型的數(shù)字48，在運(yùn)算過程中等同于int。所以將字符型數(shù)字‘1’轉(zhuǎn)化為整型數(shù)字1：‘1’-‘0’=1相當(dāng)于49-48 = 1。

② 時(shí)刻警惕“野指針”

在程序編寫完成后，調(diào)試過程中卻不斷報(bào)錯(cuò)：“C4700：使用了未初始化的局部變量‘OPTR’和‘OPRD’”，在查閱資料并多番詢問后。最終找出錯(cuò)誤：缺少如下代碼：

SqStack* OPTR = (SqStack*)malloc(sizeof(SqStack));

SqStack* OPND = (SqStack*)malloc(sizeof(SqStack));

換言之，我在初始化OPTR和OPND兩個(gè)順序棧的指針時(shí)，沒有給指針分配地址空間，而讓他們成為“野指針”。我一直存在一個(gè)思維誤區(qū)：我需要開辟空間給棧存放數(shù)據(jù)，并將棧的地址返回給它的指針，也就是OPTR和OPTD。存放數(shù)據(jù)固然要開辟空間，但是存放這些數(shù)據(jù)的地址也同樣要開辟空間。我就是因?yàn)闆]有給棧的地址開辟空間存放而報(bào)錯(cuò)。之后的編程，要時(shí)刻警惕野指針的存在。

③ 自定義頭文件

如果在一個(gè)文件中，寫上成百上千行的代碼，這些代碼閱讀起來(lái)就會(huì)很麻煩。因此，我們可以引入頭文件，把自己寫的函數(shù)放入頭文件中，然后直接調(diào)用到主程序中，這樣在主程序中看起來(lái)就比較清晰。本次實(shí)驗(yàn)，我將棧的定義及其相關(guān)操作單獨(dú)放在一個(gè)頭文件中，并在主程序的頭部調(diào)用，這樣主程序就只剩下與計(jì)算相關(guān)的函數(shù)，整個(gè)程序脈絡(luò)更為清晰，可讀性更高。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-745519.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】利用順序棧/鏈棧完成表達(dá)式求值（C語(yǔ)言實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！