表达式求值

Myth丶恋晨 2022-08-25 05:28 221阅读 0赞

\#define TRUE 1  
\#define FALSE 0  
\#define STACK\_INIT\_SIZE 10002

\#include "iostream"  
\#include "cstdlib"  
\#include "cstdio"  
\#include "cstring"

using namespace std;

typedef int Status; //Status 相当于 int  
typedef struct Stack1 //运算符栈  
\{  
char \* base;  
char \* top;  
\}SqStack1;  
typedef struct Stack2  //数字栈  
\{  
double \* base;  
double \* top;  
\}SqStack2;

//运算符栈操作  
void  InitStack1(SqStack1 &S) //创建一个空栈  
\{

S.base = (char \*)malloc(sizeof(char) \* STACK\_INIT\_SIZE);  
S.top = S.base;  
\}  
Status Stack1Empty(SqStack1 S)//判断是否为空  
\{  
if(S.top == S.base) return TRUE;  
else return FALSE;  
\}  
void Push1(SqStack1 &S,char e )//插入元素e为新的栈顶元素  
\{  
\* S.top++ = e;  
\}  
void Pop1(SqStack1 &S,char &e)//出栈  
\{  
e = \* --S.top ;  
\}  
char GetTop1(SqStack1 S)  
\{  
return \*(S.top-1);  
\}  
void TraverseStack1(SqStack1 S)//输出当前顺序表  
\{  
char \* p = S.base;  
cout<<"运算栈中的元素为：";  
while( p != S.top  )  
\{  
cout<<\*p<<" ";  
p++;  
\}  
cout<<endl;  
\}

//数字栈操作  
void  InitStack2(SqStack2 &S) //创建一个空栈  
\{

S.base = (double \*)malloc(sizeof(double) \* STACK\_INIT\_SIZE);  
S.top = S.base;  
\}  
void Push2(SqStack2 &S,double e )//插入元素e为新的栈顶元素  
\{  
\* S.top++ = e;  
\}  
void Pop2(SqStack2 &S,double &e)//出栈  
\{  
e = \* --S.top ;  
\}  
double GetTop2(SqStack2 S)  
\{  
return \*(S.top-1);  
\}  
void TraverseStack2(SqStack2 S)//输出当前顺序表  
\{  
double \* p = S.base;  
cout<<"数字栈栈中的元素为：";  
while( p != S.top  )  
\{  
cout<<\*p<<" ";  
p++;  
\}  
cout<<endl;  
\}

//运算操作  
Status In(char ch)//判断ch是否为运算符  
\{  
if(ch == '+' || ch == '('|| ch == '-' || ch == '\*' || ch == '/' || ch == ')'  || ch == '=') return TRUE;  
else return FALSE;  
\}  
char Precede(char a, char b) // 计算运算符优先级  
\{  
char r;  
switch(b)  
\{  
case '+' ://此处由于加减几乎优先级一样，故放在一起  
case '-' :  
if (a=='(' || a=='=') r = '<';  
else r = '>';  
break;  
case '\*' ://此处由于乘除优先级一样，故放在一起  
case '/' :  
if (a=='\*' || a=='/' || a==')')  
r = '>';  
else r = '<';  
break;  
case '(' : r = '<';  
break;  
case ')' :  
if (a=='(') r = '=';  
else r = '>';  
break;  
case'=':  
if (a=='=') r = '=';  
else r = '>';  
break;  
\}  
return r;  
\}  
double Operate(double a,char theta, double b)  
\{  
switch (theta)  
\{  
case '+': return a + b;break;  
case '-': return a - b;break;  
case '\*': return a \* b;break;  
case '/': return a / b;break;  
default : return FALSE;  
\}  
\}  
void Evaluateexpression\_r()  
\{  
cout<<"++++++++++请输入表达式，以 = 结束（例：1.000+2/4= ）+++++++++++++"<<endl;  
char str\[300\];  
cin>>str;  
char \*p = str;  
SqStack1 OPTR;  
SqStack2 OPND;  
InitStack1(OPTR); //设OPTR和OPND分别为运算符栈和运算数栈  
InitStack2(OPND);  
Push1(OPTR,'=');  
char x,theta,c;  
double a,b,k,t,m;  
c = \*p;  
while( !Stack1Empty(OPTR))  
\{  
if(!In(c) )  
\{  
for(k = 0; !In(c) && c!='.'; c = \* ++p)  
k = 10\*k + c-'0';  
t = 0 ;  
if(c=='.')  
\{  
c = \* ++p;  
for(t = 0,m = 0.1 ; !In(c)  ; c = \* ++p)  
\{  
t += m \* (c-'0');  
m \*= 0.1;  
\}  
\}  
Push2(OPND,k+t);  
\}  
else  
\{  
switch(Precede(GetTop1(OPTR),c))  
\{  
case '<':  
Push1(OPTR,c);  
c = \* ++p;  
break;  
case '=':  
Pop1(OPTR,x);  
c = \* ++p;  
break;  
case '>':  
Pop1(OPTR,theta);  
Pop2(OPND,b); Pop2(OPND,a);  
Push2(OPND,Operate(a,theta,b));  
break;  
\}  
\}  
\}  
printf("表达式结果： %s%.3lf\\n",str,GetTop2(OPND));  
\}  
int main()  
\{  
int door = 1;  
do\{  
Evaluateexpression\_r();  
cout<<"是否要继续检测下一组括号(Y/N)：";  
char ch;  
cin>>ch;  
if(ch == 'N'|| ch == 'n') door = 0;  
\}while(door);  
  
return 0;  
\}