C語(yǔ)言中棧和隊(duì)列實(shí)現(xiàn)表達(dá)式求值的實(shí)例
更新時(shí)間：2017年08月14日 10:09:56 投稿：lqh
這篇文章主要介紹了C語(yǔ)言中棧和隊(duì)列實(shí)現(xiàn)表達(dá)式求值的實(shí)例的相關(guān)資料,這里主要是對(duì)數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的理解和應(yīng)用，需要的朋友可以參考下
C語(yǔ)言中棧和隊(duì)列實(shí)現(xiàn)表達(dá)式求值的實(shí)例
實(shí)現(xiàn)代碼：
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define STACK_SIZE 20
#define STACK_INCREMENT 10
#define QUEUE_SIZE 20
typedef int Status;
typedef char StackElemtype;
typedef struct Stack{
StackElemtype* base;
StackElemtype* top;
int stackSize;
}Stack;
Status StackInit(Stack* s){
s->base = (StackElemtype*)malloc(sizeof(StackElemtype) * STACK_SIZE);
if( !s->base )
return ERROR;
s->top = s->base;
s->stackSize = STACK_SIZE;
return OK;
}
Status Pop(Stack* s,StackElemtype* value){
if( s->base == s->top ){
printf("\nstack empty\n");
return ERROR;
}
*value = *(--(s->top));
return OK;
}
Status Push(Stack* s,StackElemtype value){
if( s->top - s->base == s->stackSize){
s->base = (StackElemtype*)realloc(s->base,sizeof(StackElemtype) * (STACK_INCREMENT + STACK_SIZE));
if( !s->base )
return ERROR;
s->top = s->base + STACK_SIZE;
s->stackSize = STACK_SIZE + STACK_INCREMENT;
}
*(s->top) = value;
s->top++;
return OK;
}
int StackLength(Stack s){
return s.top - s.base;
}
typedef double StackElemtype_ForValueExperssion;
typedef struct Stack_2{
StackElemtype_ForValueExperssion* base;
StackElemtype_ForValueExperssion* top;
int stackSize;
}Stack_2;
Status StackInit_2(Stack_2* s){
s->base = (StackElemtype_ForValueExperssion*)malloc(sizeof(StackElemtype_ForValueExperssion) * STACK_SIZE);
if( !s->base )
return ERROR;
s->top = s->base;
s->stackSize = STACK_SIZE;
return OK;
}
Status Pop_2(Stack_2* s,StackElemtype_ForValueExperssion* value){
if( s->base == s->top ){
printf("\nstack empty\n");
return ERROR;
}
*value = *(--(s->top));
return OK;
}
Status Push_2(Stack_2* s,StackElemtype_ForValueExperssion value){
if( s->top - s->base == s->stackSize){
s->base = (StackElemtype_ForValueExperssion*)realloc(s->base,sizeof(StackElemtype_ForValueExperssion) * (STACK_INCREMENT + STACK_SIZE));
if( !s->base )
return ERROR;
s->top = s->base + STACK_SIZE;
s->stackSize = STACK_SIZE + STACK_INCREMENT;
}
*(s->top) = value;
s->top++;
return OK;
}
typedef double QueueElemtype;
typedef char QueueOperatorValue;
typedef struct QueueNode{
QueueElemtype data;
QueueOperatorValue operator;
struct QueueNode* next;
int flag;
}QueueNode,*QueueNodePtr;
typedef struct Queue{
QueueNodePtr front;
QueueNodePtr rear;
}Queue;
Status QueueInit(Queue* q){
q->front = (QueueNodePtr)malloc(sizeof(QueueNode));
if( !q->front )
return ERROR;
q->rear = q->front;
q->rear->next = NULL;
return OK;
}
Status QueueInsert(Queue* q,QueueElemtype value){
QueueNodePtr new;
new = (QueueNodePtr)malloc(sizeof(QueueNode));
if( !new )
return ERROR;
new->data = value;
new->flag = 1;
new->next = NULL;
q->rear->next = new;
q->rear = new;
return OK;
}
Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value){
QueueNodePtr new;
new = (QueueNodePtr)malloc(sizeof(QueueNode));
if( !new )
return ERROR;
new->operator = value;
new->flag = 0;
new->next = NULL;
q->rear->next = new;
q->rear = new;
return OK;
}
Status QueueDelete(Queue* q,QueueElemtype* value,QueueOperatorValue *operator,int* symbol){
QueueNodePtr first;
if( q->front == q->rear )
return ERROR;
first = q->front->next;
if( first->flag == 1 ){
*value = first->data;
*symbol = 1;
}
else{
*operator = first->operator;
*symbol = 0;
}
q->front->next = first->next;
if( first == q->rear ){
q->rear = q->front;
}
return OK;
}
/* 利用棧將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式：
* ——————————————————————————————————————————————————————————————
* | 用戶的輸入 | 進(jìn)行的處理 |
* | 0~9： | 直接輸出到控制臺(tái) |
* | /，*，( | 直接Push |
* | +，- | 將棧中的元素Pop直到1.?？栈蛘呤?.遇到( |
* | ) | 在遇到(之前將棧中的元素全部Pop |
* ——————————————————————————————————————————————————————————————
* */
Status Infix2Postfix(Queue* q){
//Queue q;
//QueueInit(&q);
Stack s;
StackInit(&s);
char c,e;
char bufferDigit[10];
int i = 0;
double longDigit;
printf(" Please Enter Infix Expression\n");
printf("------------NOTE: end of '#'--------------\n");
scanf("%c", &c);
while( '#' != c){
while( c <= '9' && c >= '0' || '.' == c ){
bufferDigit[i++] = c;
bufferDigit[i] = '\0';
scanf("%c", &c);
if(!((c <= '9' && c >= '0' ) || '.' == c )){
longDigit = atof(bufferDigit);
QueueInsert(q,longDigit);
i = 0;
}
}
if( '(' == c || '*' == c || '/' == c ){
Push(&s, c);
}
else if( '+' == c || '-' == c ){
if( !StackLength(s) )
Push(&s, c);
else{
Pop(&s, &e);
while( '(' != e ){
QueueInsert_operatorValue(q, e);
if( StackLength(s) == 0 ){
break;
}else
Pop(&s, &e);
}
if( '(' == e )
Push(&s, e);
Push(&s, c);
}
}else if( ')' == c ){
Pop(&s, &e);
while( '(' != e ){
QueueInsert_operatorValue(q, e);
Pop(&s, &e);
}
}else if( '#' == c){
break;
}else{
printf("input ERROR!\n");
return ERROR;
}
scanf("%c", &c);
}
while(StackLength(s)){
Pop(&s, &e);
QueueInsert_operatorValue(q, e);
}
QueueInsert_operatorValue(q,'#');
return OK;
}
Status ShowQueue(Queue q){
printf("The Reverse Polish Notation is:");
if(q.front == q.rear){
printf("Queue Empty");
return ERROR;
}
QueueNodePtr p = q.front->next;
while(p != q.rear){
if(p->flag)
printf("%g ", p->data);
else
printf("%c ", p->operator);
p = p->next;
}
printf("\n");
return OK;
}
/* 利用棧求解后綴表達(dá)式(逆波蘭表達(dá)式)的值。
* ——————————————————————————————————————————————————————————————————————
* | +，-，*，/， | 將棧頂?shù)膬蓚€(gè)元素彈出進(jìn)行計(jì)算，將結(jié)果壓入棧頂 |
* | 數(shù)字 | 將其壓入棧頂 |
* ———————————————————————————————————————————————————————————————————————
* */
Status ValueExpression(Queue q){
Stack_2 s;
StackInit_2(&s);
double o1;
double o2;
QueueElemtype number;
QueueOperatorValue operator;
int symbol;
QueueDelete(&q,&number,&operator,&symbol);
while( symbol == 1 || ( symbol == 0 && '#' != operator)){
if(symbol == 1){
Push_2(&s, number);
}
else if(symbol == 0){
switch(operator){
case '+':
Pop_2(&s,&o1);
Pop_2(&s,&o2);
Push_2(&s,o2 + o1);
break;
case '-':
Pop_2(&s,&o1);
Pop_2(&s,&o2);
Push_2(&s,o2 - o1);
break;
case '*':
Pop_2(&s,&o1);
Pop_2(&s,&o2);
Push_2(&s,o2 * o1);
break;
case '/':
Pop_2(&s,&o1);
Pop_2(&s,&o2);
Push_2(&s,o2 / o1);
break;
}
}
QueueDelete(&q,&number,&operator,&symbol);
}
Pop_2(&s,&o1);
printf("The Value of the Expression is %g\n",o1);
return OK;
}
int main(){
Queue q;
QueueInit(&q);
Infix2Postfix(&q);
ShowQueue(q);
/*
QueueElemtype number;
QueueOperatorValue operator;
int symbol;
QueueDelete(&q,&number,&operator,&symbol);
printf("%f,%c,%d\n",number,operator,symbol);
*/
ValueExpression(q);
//Stack
/*
Stack s;
StackInit(&s);
StackElemtype c;
Push(&s,'1');
Push(&s,'2');
Push(&s,'3');
Push(&s,'4');
Pop(&s,&c);
printf("%c ", c);
Pop(&s,&c);
printf("%c ", c);
Pop(&s,&c);
printf("%c ", c);
Pop(&s,&c);
printf("%c ", c);
*/
//Queue
/*
Queue q;
QueueElemtype c;
QueueInit(&q);
QueueInsert(&q,1);
QueueInsert(&q,2);
QueueInsert(&q,3);
QueueInsert(&q,4);
QueueDelete(&q,&c);
printf("%d ", c);
QueueDelete(&q,&c);
printf("%d ", c);
QueueDelete(&q,&c);
printf("%d ", c);
QueueDelete(&q,&c);
printf("%d ", c);
if(QueueDelete(&q,&c)){
printf("%d ",c);
}
*/
/*
Queue q;
QueueInit(&q);
QueueInsert(&q,2.1);
QueueInsert_operatorValue(&q,'+');
QueueInsert(&q,43.1);
QueueInsert_operatorValue(&q,'a');
QueueInsert_operatorValue(&q,'(');
int iswho;
double d;
char c;
QueueDelete(&q,&d,&c,&iswho);
if(iswho == 1)
printf("%f ",d);
else
printf("%c ", c);
QueueDelete(&q,&d,&c,&iswho);
if(iswho == 1)
printf("%f ",d);
else
printf("%c ", c);
QueueDelete(&q,&d,&c,&iswho);
if(iswho == 1)
printf("%f ",d);
else
printf("%c ", c);
QueueDelete(&q,&d,&c,&iswho);
if(iswho == 1)
printf("%f ",d);
else
printf("%c ", c);
*/
return 0;
}
以上就是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的應(yīng)用，如有疑問(wèn)請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
您可能感興趣的文章:
- C語(yǔ)言 淺談棧與隊(duì)列的定義與操作
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)
- C語(yǔ)言編程數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列的全面講解示例教程
- C語(yǔ)言編程數(shù)據(jù)結(jié)構(gòu)的棧和隊(duì)列
- C語(yǔ)言用棧和隊(duì)列實(shí)現(xiàn)的回文檢測(cè)功能示例
- C語(yǔ)言 表、棧和隊(duì)列詳解及實(shí)例代碼
- 深入淺析C語(yǔ)言中堆棧和隊(duì)列
- C語(yǔ)言超詳細(xì)講解棧與隊(duì)列實(shí)現(xiàn)實(shí)例
相關(guān)文章
Boost是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱。Boost庫(kù)是一個(gè)可移植、提供源代碼的C++庫(kù)，作為標(biāo)準(zhǔn)庫(kù)的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱2022-11-11
C語(yǔ)言實(shí)現(xiàn)會(huì)員管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)會(huì)員管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
基于C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的掃雷小游戲
這篇文章主要為大家詳細(xì)介紹了基于C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
在Qt中使用QChart類可以快速繪制一個(gè)圖表出來(lái),比如折線圖、餅圖、柱狀圖等,本文就來(lái)為大家介紹一下如何利用QChart繪制簡(jiǎn)單的餅圖吧2024-11-11
C++共享智能指針shared_ptr的實(shí)現(xiàn)
在C++中沒有垃圾回收機(jī)制,必須自己釋放分配的內(nèi)存,否則就會(huì)造成內(nèi)存泄露,解決這個(gè)問(wèn)題最有效的方法是使用智能指針,本文主要介紹了C++共享智能指針shared_ptr的實(shí)現(xiàn),感興趣的可以了解一下2023-12-12
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)人臉檢測(cè)功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
c++如何實(shí)現(xiàn)跳表（skiplist）
這篇文章主要介紹了c++如何實(shí)現(xiàn)跳表，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-08-08
這篇文章主要介紹了計(jì)算機(jī)在材料科學(xué)中的一個(gè)練習(xí)題，功能是模擬氣化后分子沉積2013-11-11
下面小編就為大家?guī)?lái)一篇深入理解C++移位運(yùn)算符。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-05-05
C?語(yǔ)言輸入輸出庫(kù)函數(shù)講解(最新推薦)
輸入輸出函數(shù)能夠讓程序和用戶或者文件進(jìn)行交互,這篇文章主要介紹了C?語(yǔ)言輸入輸出庫(kù)函數(shù)講解,需要的朋友可以參考下2025-04-04