|
一、课程设计题目及内容 [问题描述] 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“运算符优先法”求算术表达式的值。 [基本要求] （1） 从键盘或文件读入一个合法的算术表达式，输出正确的结果。 （2） 显示输入序列和栈的变化过程。 （3） 考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。
二、程序中使用的数据结构及主要符号说明 程序中使用了堆栈，其中OPTR为运算符栈（运算符包括‘+’‘-’‘*’‘/’‘(’‘)’‘[’‘]’’{’’}’’#’），OPND为操作数栈(操作数包括‘0’’1’’2’’3’’4’‘5’‘6’‘7’‘8’‘9’) 三、程序流程图和带有注释的源程序  源代码：
#include
using namespace std;
typedef struct SNode1//运算符栈链
{
char data;
struct SNode1* next;
}StackNode1, * Linkstack1;
typedef struct SNode2//数字栈链
{
int data;
struct SNode2* next;
}StackNode2, * Linkstack2;
void InitStack1(Linkstack1& S)//初始化运算符栈链
{
S = NULL;
}
void InitStack2(Linkstack2& S)//初始化数字栈链
{
S = NULL;
}
void push1(Linkstack1& S, char ch)//运算符入栈
{
Linkstack1 p;
p = (Linkstack1)malloc(sizeof(Linkstack1));
p->data = ch;
p->next = S;
S = p;
}
void push2(Linkstack2& S, int ch)//数字入栈
{
Linkstack2 p;
p = (Linkstack2)malloc(sizeof(Linkstack2));
p->data = ch;
p->next = S;
S = p;
}
char GetTop1(Linkstack1& S)//获得运算符栈栈顶元素
{
if (S != NULL)
return S->data;
}
int GetTop2(Linkstack2& S)//获得数字符栈栈顶元素
{
if (S != NULL)
return S->data;
}
void pop1(Linkstack1& S, char& e)//用元素e存储当前运算符栈栈顶元素
{ //弹出栈顶元素,栈顶指针指向下一元素
e = GetTop1(S);
if (S != NULL)
{
S = S->next;
}
}
void pop2(Linkstack2& S, int& e)//用元素e存储当前数字栈栈顶元素
{ //弹出栈顶元素,栈顶指针指向下一元素
if (S != NULL)
{
e = GetTop2(S);
S = S->next;
}
}
int In(char ch)//In函数检测字符ch是运算符还是数字
{ //若为运算符，返回1；若为数字，返回0
switch (ch)
{
case '(':return 1;
case ')':return 1;
case '+':return 1;
case '-':return 1;
case '*':return 1;
case '/':return 1;
case '#':return 1;
case '[':return 1;
case ']':return 1;
case '{':return 1;
case '}':return 1;
default: return 0;
}
}
char Precede(char a, char b)//比较运算符优先级
{
if (b == '+')
{
if (a == '(' || a == '#' || a == '[' || a == '{') return '';
}
if (b == '-')
{
if (a == '(' || a == '#' || a == '[' || a == '{') return '';
}
if (b == '*')
{
if (a == '*' || a == '/' || a == ')' || a == ']' || a == '}') return '>';
return ' |