基于棧結(jié)構(gòu)的中綴表達(dá)式求值

1、實(shí)驗(yàn)三 基于棧結(jié)構(gòu)的中綴表達(dá)式求值班級：計(jì)科131、問題描述從鍵盤輸入一中綴表達(dá)式字符串，讀字符串，利用棧結(jié)構(gòu)實(shí)現(xiàn)表達(dá)式求值。2、輸入與輸出 輸入：從鍵盤中綴表達(dá)式如： 325×（64）輸出：計(jì)算結(jié)果423、需求分析1.定義兩個(gè)棧結(jié)構(gòu)，數(shù)棧用于存放表達(dá)式中的數(shù)，符號棧用于存放表達(dá)式中的符號，實(shí)現(xiàn)棧的運(yùn)算2.在讀數(shù)的時(shí)候考慮多位運(yùn)算 3.實(shí)現(xiàn)表達(dá)式求值4、開發(fā)工具與環(huán)境硬件設(shè)備：微型計(jì)算機(jī)系統(tǒng)軟件環(huán)境：操作系統(tǒng)Windows，開發(fā)工具VC6.0等等5、概要設(shè)計(jì)1.結(jié)構(gòu)定義 typedef struct /* 運(yùn)算符棧 */ char *base,*top; int stacksize;

2、 SqStack; typedef struct /* 運(yùn)算數(shù)棧 */ int *base,*top; int stacksize; SqStack1;int priority77='>', '>', '<', '<', '<', '>', '>', / + '>', '>', '<', '<', '<', '>'

3、;, '>', / - '>', '>', '>', '>', '<', '>', '>', / * '>', '>', '>', '>', '<', '>', '>', / / '<', '<', '<'

4、;, '<', '<', '=', , / ( '>', '>', '>', '>', ' ', '>', '>', / ) '<', '<', '<', '<', '<', ' ', '=' / #; /*用于比較符號優(yōu)先級的全局二維數(shù)組*/2各函

5、數(shù)模塊void InitStack(SqStack *s);操作結(jié)果：初始化運(yùn)算符棧。void InitStack1(SqStack *s);操作結(jié)果：初始化運(yùn)算數(shù)棧。void InitStack1(SqStack *s);操作結(jié)果：初始化運(yùn)算符棧。char GetTop(SqStack s)操作結(jié)果：若棧不空，則返回運(yùn)算符棧棧頂元素，否則返回ERROR。int GetTop1(SqStack1 s)操作結(jié)果：若棧不空，則用，否則返回ERROR。void PushS(SqStack &s, char e)操作結(jié)果：插入元素e為新的運(yùn)算符的棧頂。void PushS1(SqStack1

6、&s, int e)操作結(jié)果：插入元素e為新的運(yùn)算數(shù)棧頂。int pop(SqStack &s, char &e)操作結(jié)果：若運(yùn)算符棧不空，則刪除s的棧頂元素，用e返回其值，并返回OK,否則返回ERROR。int pop1(SqStack1 &s, int &e)操作結(jié)果：若運(yùn)算數(shù)棧不空，則刪除s的棧頂元素，用e返回其值，并返回OK,否則返回ERROR。6、程序清單#include<iostream>using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10

7、#define ERROR 0#define OK 1typedef struct /* 運(yùn)算符棧 */char *base, *top;int stacksize;SqStack;typedef struct /* 運(yùn)算數(shù)棧 */int *base, *top;int stacksize;SqStack1;int priority77 = '>', '>', '<', '<', '<', '>', '>' ,/ + 0 '>&

8、#39;, '>', '<', '<', '<', '>', '>' ,/ - 1 '>', '>', '>', '>', '<', '>', '>' ,/ * 2 '>', '>', '>', '>', '<&

9、#39;, '>', '>' ,/ / 3 '<', '<', '<', '<', '<', '=', ,/ ( 4 '>', '>', '>', '>', ' ', '>', '>' ,/ ) 5 '<', '<', '<

10、', '<', '<', ' ', '=' / # 6;/*用于比較符號優(yōu)先級的全局二維數(shù)組*/void InitStack(SqStack &s)/初始化運(yùn)算符棧s.base = (char *)malloc(STACK_INIT_SIZE*sizeof(char);if (!s.base)exit(OVERFLOW);s.top = s.base;s.stacksize = STACK_INIT_SIZE;void InitStack1(SqStack1 &s)/初始化運(yùn)算數(shù)棧s.base

11、= (int *)malloc(STACK_INIT_SIZE*sizeof(int);if (!s.base)exit(OVERFLOW);s.top = s.base;s.stacksize = STACK_INIT_SIZE;void PushS(SqStack &s, char e)/插入元素e為新的運(yùn)算符棧的棧頂if (s.top - s.base >= s.stacksize)s.base=(char *)realloc(s.base, (s.stacksize + STACKINCREMENT)*sizeof(char);if (!s.base)exit(OVERF

12、LOW);s.top = s.base + s.stacksize;/指向棧頂s.stacksize += STACKINCREMENT;*s.top+ = e;void PushS1(SqStack1 &s, int e)/插入元素e為新的運(yùn)算數(shù)的棧頂if (s.top - s.base >= s.stacksize)s.base = (int *)realloc(s.base, (s.stacksize + STACKINCREMENT)*sizeof(int);if (!s.base)exit(OVERFLOW);s.top = s.base + s.stacksize;/

13、指向棧頂s.stacksize += STACKINCREMENT;*s.top+ = e;/Pushchar GetTop(SqStack s)/若棧不空，則返回s的棧頂元素，否則返回ERRORif (s.top = s.base) return ERROR;return *(s.top - 1);int GetTop1(SqStack1 s)/若棧不空，則用e返回s的棧頂元素，否則返回ERRORif (s.top = s.base) return ERROR;return *(s.top - 1);int pop(SqStack &s, char &e)/若棧不空，則刪除s

14、的棧頂元素，用e返回其值if (s.top = s.base) return ERROR;e = *-s.top;return OK;int pop1(SqStack1 &s, int &e)/若棧不空，則刪除s的棧頂元素，用e返回其值if (s.top = s.base) return ERROR;e = *-s.top;return OK;int number(char a)/將運(yùn)算符的位置轉(zhuǎn)化為數(shù)字以便于在二維數(shù)組中找到優(yōu)先級switch (a)case '+': return 0;break;case '-': return 1;brea

15、k;case '*': return 2;break;case '/': return 3;break;case '(': return 4;break;case ')': return 5;break;case '#': return 6;break;default:return ERROR;char precede(char a, char b)int i, j;i = number(a);j = number(b);return priorityij;int Operate(int a, char c, in

16、t b)/計(jì)算表達(dá)式結(jié)果并返回其值switch (c)case'+':return a + b;case'-':return a - b;case'*':return a*b;case'/':return a / b; default: return ERROR;int input(SqStack &s, SqStack1 &s1)/完成表達(dá)式的輸入與計(jì)算char c1, c2;char temp;int e, a, b;c1 = getchar();while (c1 != '#' | GetTo

17、p(s) != '#')if (c1 >= '0'&&c1 <= '9')c2 = getchar();if (c2 != '#'&&c2 >= '0'&&c2 <= '9')/c2為數(shù)字e = (int)c1 - 48) * 10 + (int)c2 - 48;PushS1(s1, e);/內(nèi)層ifelse/c1為運(yùn)算數(shù)，c2為運(yùn)算符 else1PushS1(s1, (int)c1 - 48);/將運(yùn)算數(shù)入棧again:if

18、(c2 != '#' | GetTop(s) != '#')switch (precede(GetTop(s), c2)case'<':/棧頂元素優(yōu)先權(quán)低PushS(s, c2);/c1 = getchar();break;case'=':/脫括號并接收下一個(gè)字符pop(s, c2);/c1 = getchar();break;case'>':/退棧并將運(yùn)算結(jié)果入棧pop(s, temp);pop1(s1, b);pop1(s1, a);PushS1(s1, Operate(a, temp, b);goto again;/switch/ifelsegoto exit;/計(jì)算完成晚會(huì)結(jié)果/內(nèi)層else/ifelseaga:if (c1 != '#' | GetTop(s) != '#')switch (precede(GetTop(s), c1)case'<