Question

数据结构：利用栈来实现算术表达式求值的算法。

使用键盘输入表达式字符序列，对于语法正确、不含变量的整数表达式，利用给定的运算符优先关系，实现表达式的求值。
具体功能包括：
程序运行时，输入合法的算术表达式，便可输出相应的计算结果。其中，表达式数据、中间值及最终结果包括数字、加减乘除和括号。

实现提示：
1. 将栈的定义和实现单独保存在头文件“stack.h”中，然后在表达式求值的源程序中包含此头文件（即#include“stack.h”）。
2.表达式求值源程序的具体实现
(1) 主函数完成表达式的输入和计算结果的输出。
(2) 函数EvaluateExpression的实现见算法3.4。
(3) 函数In(c)的实现可以采用以下方式：
Status In(SElemType c)// 应在前面有定义typedef char SElemType;
{ // 判断c是否为运算符
switch(c)
{
case'+':return TRUE;
……//补充完整
default:return FALSE;
}
}
(4) 函数Precede(t1,t2)的实现可以采用以下形式：
SElemType Precede(SElemType t1,SElemType t2)
{ //根据教材表3.1，判断两个运算符的优先关系
SElemType f;
switch(t2)
{
case '+':
case '-':if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
……//补充完整
}
return f;
}
(5) 函数Operate(a,theta,b)的实现可以采用以下方式：
SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
SElemType c;
a=a-48;
b=b-48;
switch(theta)
{
case'+':c=a+b+48;
break;
……//补充完整
}
return c;
}
帮忙写下EvaluateExpression 和主函数就可以拉

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define error 0
#define ok 1
#define overflow -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OPSETSIZE 7
char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#'};
unsigned char Prior[7][7] = { // 算符间的优先关系
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=',' ',
'>','>','>','>',' ','>','>',
'<','<','<','<','<',' ','='
};
typedef int Status;

template <typename T>
struct SqStack
{
T *top;
T *base;
int stacksize;

};//顺序栈结构模板

template <typename T1,typename T2>
Status InitStack(T1 &S)
{
S.base=(T2 *)malloc(STACK_INIT_SIZE*sizeof(T2));
if(!S.base) exit (overflow);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return ok;
}//初始化栈函数模板

template <typename T1,typename T2>
Status Push(T1 &S,T2 e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(T2 *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(T2));
if(!S.base) exit (overflow);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return ok;
}//入栈函数模板

template <typename T1,typename T2>
Status Pop(T1 &S,T2 &e)
{
if(S.top==S.base) return error;
e=*--S.top;
return ok;
}//出栈函数模板

template <typename T1,typename T2>
T2 GetTop(T1 S)
{
if(S.top==S.base)
return error;
else
return *(S.top-1);

}//获取栈顶元素模板

Status In(char Test,char* TestOp) {
bool Find=false;
for (int i=0; i< OPSETSIZE; i++) {
if (Test == TestOp[i]) Find= true;
}
return Find;
}//判断是否为运算符

float Operate(float a,unsigned char theta, float b) {
switch(theta) {
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
default : return 0;
}
}//运算

int ReturnOpOrd(char op,char* TestOp) {
int i;
for(i=0; i< OPSETSIZE; i++) {
if (op == TestOp[i]) return i;
}
return 0;
}

char precede(char Aop, char Bop) {
return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];
}//ReturnOpOrd和precede组合，判断运算符优先级

float EvaluateExpression() {
// 算术表达式求值的算符优先算法。
// 设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。
SqStack<char> OPTR; // 运算符栈，字符元素
SqStack<float> OPND; // 运算数栈，实数元素
char TempData[20];
float Data,a,b;
char theta,c,x,Dr[2];

InitStack<SqStack<char>,char> (OPTR);
Push (OPTR, '#');
InitStack <SqStack<float>,float>(OPND);
strcpy(TempData,"\0");//将TempData置为空
c=getchar();
while (c!= '#' || GetTop<SqStack<char>,char>(OPTR)!= '#')
{
if (!In(c, OPSET))
{
Dr[0]=c;
Dr[1]='\0';//存放单个数
strcat(TempData,Dr);//将单个数连到TempData中，形成字符串
c=getchar();
if(In(c,OPSET))//如果遇到运算符，则将字符串TempData转换成实数，入栈，
并重新置空
{
Data=(float)atof(TempData);
Push(OPND, Data);
strcpy(TempData,"\0");
}
}
else
{ // 不是运算符则进栈
switch (precede(GetTop<SqStack<char>,char>(OPTR), c)) {
case '<': // 栈顶元素优先权低
Push(OPTR, c);
c=getchar();
break;
case '=': // 脱括号并接收下一字符
Pop(OPTR, x);
c=getchar();
break;
case '>': // 退栈并将运算结果入栈
Pop(OPTR, theta);
Pop(OPND, b);
Pop(OPND, a);
Push(OPND, Operate(a, theta, b));
break;
} // switch
}
} // while
return GetTop<SqStack<float>,float>(OPND);
} // EvaluateExpression

void main()
{
printf("请输入表达式（end #）：\n");
printf("%f\n",EvaluateExpression());
}

给你一个完全的程序，本人自己写的。

Answer 2

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#define
error
0
#define
ok
1
#define
overflow
-1
#define
STACK_INIT_SIZE
100
#define
STACKINCREMENT
10
#define
OPSETSIZE
7
char
OPSET[OPSETSIZE]={'+','-','*','/','(',')','#'};
unsigned
char
Prior[7][7]
=
{
//
算符间的优先关系
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=','
',
'>','>','>','>','
','>','>',
'<','<','<','<','<','
','='
};
typedef
int
Status;
template
<typename
T>
struct
SqStack
{
T
*top;
T
*base;
int
stacksize;
};//顺序栈结构模板
template
<typename
T1,typename
T2>
Status
InitStack(T1
&S)
{
S.base=(T2
*)malloc(STACK_INIT_SIZE*sizeof(T2));
if(!S.base)
exit
(overflow);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return
ok;
}//初始化栈函数模板
template
<typename
T1,typename
T2>
Status
Push(T1
&S,T2
e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(T2
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(T2));
if(!S.base)
exit
(overflow);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return
ok;
}//入栈函数模板
template
<typename
T1,typename
T2>
Status
Pop(T1
&S,T2
&e)
{
if(S.top==S.base)
return
error;
e=*--S.top;
return
ok;
}//出栈函数模板
template
<typename
T1,typename
T2>
T2
GetTop(T1
S)
{
if(S.top==S.base)
return
error;
else
return
*(S.top-1);
}//获取栈顶元素模板
Status
In(char
Test,char*
TestOp)
{
bool
Find=false;
for
(int
i=0;
i<
OPSETSIZE;
i++)
{
if
(Test
==
TestOp[i])
Find=
true;
}
return
Find;
}//判断是否为运算符
float
Operate(float
a,unsigned
char
theta,
float
b)
{
switch(theta)
{
case
'+':
return
a+b;
case
'-':
return
a-b;
case
'*':
return
a*b;
case
'/':
return
a/b;
default
:
return
0;
}
}//运算
int
ReturnOpOrd(char
op,char*
TestOp)
{
int
i;
for(i=0;
i<
OPSETSIZE;
i++)
{
if
(op
==
TestOp[i])
return
i;
}
return
0;
}
char
precede(char
Aop,
char
Bop)
{
return
Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];
}//ReturnOpOrd和precede组合，判断运算符优先级
float
EvaluateExpression()
{
//
算术表达式求值的算符优先算法。
//
设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。
SqStack<char>
OPTR;
//
运算符栈，字符元素
SqStack<float>
OPND;
//
运算数栈，实数元素
char
TempData[20];
float
Data,a,b;
char
theta,c,x,Dr[2];
InitStack<SqStack<char>,char>
(OPTR);
Push
(OPTR,
'#');
InitStack
<SqStack<float>,float>(OPND);
strcpy(TempData,"\0");//将TempData置为空
c=getchar();
while
(c!=
'#'
||
GetTop<SqStack<char>,char>(OPTR)!=
'#')
{
if
(!In(c,
OPSET))
{
Dr[0]=c;
Dr[1]='\0';//存放单个数
strcat(TempData,Dr);//将单个数连到TempData中，形成字符串
c=getchar();
if(In(c,OPSET))//如果遇到运算符，则将字符串TempData转换成实数，入栈，
并重新置空
{
Data=(float)atof(TempData);
Push(OPND,
Data);
strcpy(TempData,"\0");
}
}
else
{
//
不是运算符则进栈
switch
(precede(GetTop<SqStack<char>,char>(OPTR),
c))
{
case
'<':
//
栈顶元素优先权低
Push(OPTR,
c);
c=getchar();
break;
case
'=':
//
脱括号并接收下一字符
Pop(OPTR,
x);
c=getchar();
break;
case
'>':
//
退栈并将运算结果入栈
Pop(OPTR,
theta);
Pop(OPND,
b);
Pop(OPND,
a);
Push(OPND,
Operate(a,
theta,
b));
break;
}
//
switch
}
}
//
while
return
GetTop<SqStack<float>,float>(OPND);
}
//
EvaluateExpression
void
main()
{
printf("请输入表达式（end
#）：\n");
printf("%f\n",EvaluateExpression());
}
给你一个完全的程序，本人自己写的。