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

1、实验三 基于栈结构的中缀表达式求值班级：计科131、问题描述从键盘输入一中缀表达式字符串，读字符串，利用栈结构实现表达式求值。2、输入与输出 输入：从键盘中缀表达式如： 325×（64）输出：计算结果423、需求分析1.定义两个栈结构，数栈用于存放表达式中的数，符号栈用于存放表达式中的符号，实现栈的运算2.在读数的时候考虑多位运算 3.实现表达式求值4、开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具VC6.0等等5、概要设计1.结构定义 typedef struct /* 运算符栈 */ char *base,*top; int stacksize;

2、 SqStack; typedef struct /* 运算数栈 */ int *base,*top; int stacksize; SqStack1;int priority77='>', '>', '<', '<', '<', '>', '>', / + '>', '>', '<', '<', '<', '>'

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

4、;, '<', '<', '=', , / ( '>', '>', '>', '>', ' ', '>', '>', / ) '<', '<', '<', '<', '<', ' ', '=' / #; /*用于比较符号优先级的全局二维数组*/2各函

5、数模块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

6、&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、程序清单#include<iostream>using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10

7、#define ERROR 0#define OK 1typedef struct /* 运算符栈 */char *base, *top;int stacksize;SqStack;typedef struct /* 运算数栈 */int *base, *top;int stacksize;SqStack1;int priority77 = '>', '>', '<', '<', '<', '>', '>' ,/ + 0 '>&

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

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

10、', '<', '<', ' ', '=' / # 6;/*用于比较符号优先级的全局二维数组*/void InitStack(SqStack &s)/初始化运算符栈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)/初始化运算数栈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为新的运算符栈的栈顶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为新的运算数的栈顶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)/将运算符的位置转化为数字以便于在二维数组中找到优先级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)/计算表达式结果并返回其值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 != '#' | GetTo

17、p(s) != '#')if (c1 >= '0'&&c1 <= '9')c2 = getchar();if (c2 != '#'&&c2 >= '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

18、(c2 != '#' | GetTop(s) != '#')switch (precede(GetTop(s), c2)case'<':/栈顶元素优先权低PushS(s, c2);/c1 = getchar();break;case'=':/脱括号并接收下一个字符pop(s, c2);/c1 = getchar();break;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'<