中綴轉后綴

#include <stdio.h> #include <stdlib.h>#define STACK_INIT_SIZE 20 #define STACKINCREMENT 10typedef char ElemType; typedef struct {ElemType *base;ElemType *top;int stackSize; }sqStack;InitStack(sqStack *s) {s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if( !s->base )exit(0);s->top = s->base;s->stackSize = STACK_INIT_SIZE; }Push(sqStack *s, ElemType e) {// 棧滿，追加空間，魚油必須懂！if( s->top - s->base >= s->stackSize ){s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));if( !s->base )exit(0);s->top = s->base + s->stackSize;s->stackSize = s->stackSize + STACKINCREMENT;}*(s->top) = e; // 存放數據s->top++; }Pop(sqStack *s, ElemType *e) {if( s->top == s->base )return;*e = *--(s->top); // 將棧頂元素彈出并修改棧頂指針 }int StackLen(sqStack s) {return (s.top - s.base); }int main() {sqStack s;char c, e;InitStack( &s );printf("請輸入中綴表達式，以#作為結束標志：");scanf("%c", &c);while( c != '#' ){while( c>='0' && c<='9' ){printf("%c", c);scanf("%c", &c);if( c<'0' || c>'9' ){printf(" ");}}if( ')' == c ){Pop(&s, &e);while( '(' != e ){printf("%c ", e);Pop(&s, &e);}}else if( '+'==c || '-'==c ){if( !StackLen(s) ){Push(&s, c);}else{do{Pop(&s, &e);if( '(' == e ){Push(&s, e);}else{printf("%c ", e);}}while( StackLen(s) && '('!=e );Push(&s, c);}}else if( '*'==c || '/'==c || '('==c ){Push(&s, c);}else if( '#'== c ){break;}else{printf("\n出錯：輸入格式錯誤！\n");return -1;}scanf("%c", &c);}while( StackLen(s) ){Pop(&s, &e);printf("%c ", e);}return 0; }

后綴求值

#include <stdio.h> #include <ctype.h> #include <stdlib.h>#define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 #define MAXBUFFER 10typedef double ElemType; typedef struct {ElemType *base;ElemType *top;int stackSize; }sqStack;InitStack(sqStack *s) {s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if( !s->base )exit(0);s->top = s->base;s->stackSize = STACK_INIT_SIZE; }Push(sqStack *s, ElemType e) {// 棧滿，追加空間，魚油必須懂！if( s->top - s->base >= s->stackSize ){s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));if( !s->base )exit(0);s->top = s->base + s->stackSize;s->stackSize = s->stackSize + STACKINCREMENT;}*(s->top) = e; // 存放數據s->top++; }Pop(sqStack *s, ElemType *e) {if( s->top == s->base )return;*e = *--(s->top); // 將棧頂元素彈出并修改棧頂指針 }int StackLen(sqStack s) {return (s.top - s.base); }int main() {sqStack s;char c;double d, e;char str[MAXBUFFER];int i = 0;InitStack( &s );printf("請按逆波蘭表達式輸入待計算數據，數據與運算符之間用空格隔開，以#作為結束標志: \n");scanf("%c", &c);while( c != '#' ){while( isdigit(c) || c=='.' ) // 用于過濾數字{str[i++] = c;str[i] = '\0';if( i >= 10 ){printf("出錯：輸入的單個數據過大！\n");return -1;}scanf("%c", &c);if( c == ' ' ){d = atof(str);Push(&s, d);i = 0;break;}}switch( c ){case '+':Pop(&s, &e);Pop(&s, &d);Push(&s, d+e);break;case '-':Pop(&s, &e);Pop(&s, &d);Push(&s, d-e);break;case '*':Pop(&s, &e);Pop(&s, &d);Push(&s, d*e);break;case '/':Pop(&s, &e);Pop(&s, &d);if( e != 0 ){Push(&s, d/e);}else{printf("\n出錯：除數為零！\n");return -1;}break;}scanf("%c", &c);}Pop(&s, &d);printf("\n最終的計算結果為：%f\n", d);return 0; }// 5 - (6 + 7) * 8 + 9 / 4 // 5 - 13 * 8 + 9 / 4 // 5 - 104 + 2.25 // -99 + 2.25 // 5 6 7 + 8 * - 9 4 / +

測試用例

請輸入中綴表達式，以#作為結束標志：(52-((28+6)/4+(25/5)6))+249#
52 28 6 + 4 / 25 5 / 6 * + - 24 9 * +

請按逆波蘭表達式輸入待計算數據，數據與運算符之間用空格隔開，以#作為結束標志:
52 28 6 + 4 / 25 5 / 6 * + - 24 9 * + #
最終的計算結果為：229.500000

總結

以上是生活随笔為你收集整理的【数据结构与算法】中缀表达式 - 后缀表达式 - 求值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。