基于栈结构的中缀表达式求值
- 格式：doc
- 大小：32.50 KB
- 文档页数：12
实验三 基于栈结构的中缀表达式求值
班级：计科13
1、问题描述
从键盘输入一中缀表达式字符串，读字符串，利用栈结构实现表达式求值。
2、输入与输出
输入：从键盘中缀表达式如： 32＋5×（6－4）
输出：计算结果42
3、需求分析
1.定义两个栈结构，数栈用于存放表达式中的数，符号栈用于存放表达式中的符号，实现栈的运算
2.在读数的时候考虑多位运算
3.实现表达式求值
4、开发工具与环境
硬件设备：微型计算机系统
软件环境：操作系统Windows，开发工具等等
5、概要设计
1.结构定义
typedef struct /* 运算符栈 */
{ char *base,*top;
int stacksize;
}SqStack;
typedef struct /* 运算数栈 */ { int *base,*top;
int stacksize;
}SqStack1;
int priority[7][7]={{'>', '>', '<', '<', '<', '>', '>'}, // +
{'>', '>', '<', '<', '<', '>', '>'}, // -
{'>', '>', '>', '>', '<', '>', '>'}, // *
{'>', '>', '>', '>', '<', '>', '>'}, // /
{'<', '<', '<', '<', '<', '=', }, // (
{'>', '>', '>', '>', ' ', '>', '>'}, // )
{'<', '<', '<', '<', '<', ' ', '='} // #
};
/*用于比较符号优先级的全局二维数组*/
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、程序清单
#include
using namespace std;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define ERROR 0
#define OK 1
typedef struct /* 运算符栈 */
{
char *base, *top;
int stacksize;
}SqStack;
typedef struct /* 运算数栈 */
{
int *base, *top;
int stacksize; }SqStack1;
int priority[7][7] = { { '>', '>', '<', '<', '<', '>', '>' },// + 0
{ '>', '>', '<', '<', '<', '>', '>' },// - 1
{ '>', '>', '>', '>', '<', '>', '>' },// * 2
{ '>', '>', '>', '>', '<', '>', '>' },// / 3
{ '<', '<', '<', '<', '<', '=', },// ( 4
{ '>', '>', '>', '>', ' ', '>', '>' },// ) 5
{ '<', '<', '<', '<', '<', ' ', '=' }// # 6
};
/*用于比较符号优先级的全局二维数组*/
void InitStack(SqStack &s)//初始化运算符栈
{
= (char *)malloc(STACK_INIT_SIZE*sizeof(char));
if (!exit(OVERFLOW);
= ;
= STACK_INIT_SIZE;
}
void InitStack1(SqStack1 &s)//初始化运算数栈
{
= (int *)malloc(STACK_INIT_SIZE*sizeof(int));
if (!exit(OVERFLOW);
= ;
= STACK_INIT_SIZE;
}
void PushS(SqStack &s, char e)//插入元素e为新的运算符栈的栈顶 {
if - >=
{
=(char *)realloc, + STACKINCREMENT)*sizeof(char));
if (!exit(OVERFLOW);
= + ;//指向栈顶
+= STACKINCREMENT;
}
*++ = e;
}
void PushS1(SqStack1 &s, int e)//插入元素e为新的运算数的栈顶
{
if - >=
{
= (int *)realloc, + STACKINCREMENT)*sizeof(int));
if (!exit(OVERFLOW);
= + ;//指向栈顶
+= STACKINCREMENT;
}
*++ = e;
}//Push
char GetTop(SqStack s)//若栈不空，则返回s的栈顶元素，否则返回ERROR
{
if == return ERROR; return * - 1);
}
int GetTop1(SqStack1 s)//若栈不空，则用e返回s的栈顶元素，否则返回ERROR
{
if == return ERROR;
return * - 1);
}
int pop(SqStack &s, char &e)//若栈不空，则删除s的栈顶元素，用e返回其值
{
if == return ERROR;
e = *;
return OK;
}
int pop1(SqStack1 &s, int &e)//若栈不空，则删除s的栈顶元素，用e返回其值
{
if == return ERROR;
e = *;
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 priority[i][j];
}
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;
