基于栈结构的中缀表达式求值

实验三 基于栈结构的中缀表达式求值班级：计科131、问题描述从键盘输入一中缀表达式字符串，读字符串，利用栈结构实现表达式求值。2、输入与输出 输入：从键盘中缀表达式如： 325（64）输出：计算结果423、需求分析1.定义两个栈结构，数栈用于存放表达式中的数，符号栈用于存放表达式中的符号，实现栈的运算2.在读数的时候考虑多位运算 3.实现表达式求值4、开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具VC6.0等等5、概要设计1.结构定义 typedef struct /* 运算符栈 */ char *base,*top; int stacksize; SqStack; typedef struct /* 运算数栈 */ int *base,*top; int stacksize; SqStack1;int priority77=, , , , , , / + , , , , , , / - , , , , , , / * , , , , , , / / , , , , , , , , , , , / ) , , , , , , = / #; /*用于比较符号优先级的全局二维数组*/2各函数模块void InitStack(SqStack *s);操作结果：初始化运算符栈。void InitStack1(SqStack *s);操作结果：初始化运算数栈。void InitStack1(SqStack *s);操作结果：初始化运算符栈。char GetTop(SqStack s)操作结果：若栈不空，则返回运算符栈栈顶元素，否则返回ERROR。int GetTop1(SqStack1 s)操作结果：若栈不空，则用，否则返回ERROR。void PushS(SqStack &s, char e)操作结果：插入元素e为新的运算符的栈顶。void PushS1(SqStack1 &s, int e)操作结果：插入元素e为新的运算数栈顶。int pop(SqStack &s, char &e)操作结果：若运算符栈不空，则删除s的栈顶元素，用e返回其值，并返回OK,否则返回ERROR。int pop1(SqStack1 &s, int &e)操作结果：若运算数栈不空，则删除s的栈顶元素，用e返回其值，并返回OK,否则返回ERROR。6、程序清单#includeusing namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1typedef struct /* 运算符栈 */char *base, *top;int stacksize;SqStack;typedef struct /* 运算数栈 */int *base, *top;int stacksize;SqStack1;int priority77 = , , , , , ,/ + 0 , , , , , ,/ - 1 , , , , , ,/ * 2 , , , , , ,/ / 3 , , , , , , , , , , ,/ ) 5 , , , , = s.stacksize)s.base=(char *)realloc(s.base, (s.stacksize + STACKINCREMENT)*sizeof(char);if (!s.base)exit(OVERFLOW);s.top = s.base + s.stacksize;/指向栈顶s.stacksize += STACKINCREMENT;*s.top+ = e;void PushS1(SqStack1 &s, int e)/插入元素e为新的运算数的栈顶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;/指向栈顶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的栈顶元素，用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)/将运算符的位置转化为数字以便于在二维数组中找到优先级switch (a)case +: return 0;break;case -: return 1;break;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, int b)/计算表达式结果并返回其值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)/完成表达式的输入与计算char c1, c2;char temp;int e, a, b;c1 = getchar();while (c1 != # | GetTop(s) != #)if (c1 = 0&c1 = 0&c2 = 9)/c2为数字e = (int)c1 - 48) * 10 + (int)c2 - 48;PushS1(s1, e);/内层ifelse/c1为运算数，c2为运算符 else1PushS1(s1, (int)c1 - 48);/将运算数入栈again:if (c2 != # | GetTop(s) != #)switch (precede(GetTop(s), c2)case:/退栈并将运算结果入栈pop(s, temp);pop1(s1, b);pop1(s1, a);PushS1(s1, Operate(a, temp, b);goto again;/switch/ifelsegoto exit;/计算完成晚会结果/内层else/ifelseaga:if (c1 != # | GetTop(s) != #)switch (precede(GetTop(s), c1)case:/退栈并将运算结果入栈pop(s, temp);pop1(s1, b);pop1(s1, a);PushS1(s1, Operate(a, temp, b);goto aga;/switch/ifelsegoto exit;/计算结束返回结果c1 = getchar();/whileexit:return GetTop1(s1);void main()SqStack optr;/运算符栈SqStack1 opnd;/运算数栈i