實(shí)驗(yàn)2 棧和隊(duì)列的應(yīng)用-算術(shù)表達(dá)式求值

1、.1. 實(shí)驗(yàn)題目 棧和隊(duì)列的應(yīng)用2. 實(shí)驗(yàn)內(nèi)容 算術(shù)表達(dá)式求值3.實(shí)驗(yàn)?zāi)康恼莆諚：完?duì)列的概念及工作原理，運(yùn)用其原理完成實(shí)驗(yàn)題目中的內(nèi)容。4. 實(shí)驗(yàn)要求為了更好的掌握與理解課堂上老師所講的概念與原理，實(shí)驗(yàn)前要認(rèn)真預(yù)習(xí)所做的實(shí)驗(yàn)內(nèi)容及編寫源程序偽碼（寫在紙上及盤中均可）以便在實(shí)驗(yàn)課中完成老師所布置的實(shí)驗(yàn)內(nèi)容。5.概要設(shè)計(jì)原理6.詳細(xì)程序清單及注釋說明#include <stdio.h>#include <iostream.h>#include <stdlib.h>#include <string.h>#define NULL 0#define OK

2、1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 20/* 定義字符類型棧 */ typedef structint stacksize;char *base;char *top;SqStack;/* - 全局變量- */ SqStack OPTR,OPND;/ 定義運(yùn)算符棧和操作數(shù)棧char expr255; /* 存放表達(dá)式串 */char *ptr=expr;int InitStack(SqStack *s) /構(gòu)造運(yùn)算符棧 s->base=(char *)malloc(STACK_INIT_

3、SIZE*sizeof(char);if(!s->base) exit(OVERFLOW); s->top=s->base; s->stacksize=STACK_INIT_SIZE;return OK; char In(char ch) /判斷字符是否是運(yùn)算符，運(yùn)算符即返回1 return(ch='+'|ch='-'|ch='*'|ch='/'|ch='('|ch=')'|ch='#');int Push(SqStack *s,char ch) /運(yùn)算符棧插

4、入ch為新的棧頂元素*s->top=ch;s->top+;return 0;char Pop(SqStack *s) /刪除運(yùn)算符棧s的棧頂元素，用p返回其值char p;s->top-;p=*s->top;return p;char GetTop(SqStack s)/用p返回運(yùn)算符棧s的棧頂元素char p=*(s.top-1);return p;/* 判斷運(yùn)算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的 */ char Precede(char c1,char c2)int i=0,j=0;static char array49='>', '>&#

5、39;, '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', '&g

6、t;', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!', '>', '>', '>', '>', '!

7、9;, '>', '>', '<', '<', '<', '<', '<', '!', '=' switch(c1)/* i為下面array的橫標(biāo) */ case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break; case '/' : i=3;break; case '

8、(' : i=4;break; case ')' : i=5;break; case '#' : i=6;break;switch(c2) /* j為下面array的縱標(biāo) */ case '+' : j=0;break;case '-' : j=1;break;case '*' : j=2;break;case '/' : j=3;break;case '(' : j=4;break;case ')' : j=5;break;case '#'

9、: j=6;break;return (array7*i+j); /* 返回運(yùn)算符 */ /*操作函數(shù) */ int 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);return 0;int num(int n)/返回操作數(shù)的長度 char p10;itoa(n,p,10);/把整型轉(zhuǎn)換成字符串型n=strlen(

10、p);return n;int EvaluateExpression()/主要操作函數(shù) char c,theta,x; int n,m;int a,b;c = *ptr+;while(c!='#'|GetTop(OPTR)!='#') if(!In(c) if(!In(*(ptr-1) ptr=ptr-1; m=atoi(ptr);/取字符串前面的數(shù)字段 n=num(m); Push(&OPND,m);ptr=ptr+n;c=*ptr+;elseswitch(Precede(GetTop(OPTR),c) case'<':Push(

11、&OPTR,c);c=*ptr+;break; case'=':x=Pop(&OPTR);c=*ptr+;break; case'>': theta=Pop(&OPTR); b=Pop(&OPND); a=Pop(&OPND); Push(&OPND,Operate(a,theta,b);break;return GetTop(OPND);int main( )printf("請輸入正確的表達(dá)式以'#'結(jié)尾:n");dogets(expr);while(!*expr);InitStack(&OPTR); /* 初始化運(yùn)算符棧 */ Push(