表达式求值问题
拜托各位帮忙给解释一下程序设计思想和流程.非常感谢#include<iostream.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#define StackSize 100
typedef struct stack_num//有待改进
{
int top;
double a[StackSize];
}num_stack;
typedef struct stack_operation
{
int top;
char a[StackSize];
}opert;
bool empty(num_stack*p);//判断操作数栈是否为空
bool empty(opert*p);//判断操作数栈是否为空
char pop(opert*p);
double pop(num_stack*p);
void push(opert*p,char symb);
void push(num_stack*p,double num);
void PopAndTest(num_stack*p,double *x,bool*test);//.....
void PopAndTest(opert*p,char *x,bool*test);
void PushAndTest(num_stack*p,int x,bool*test);//....
void PushAndTest(opert*p,char x,bool*test);//以上为栈的实现
bool judge_of_inStr(char a[]);//判断输入的字符串是否为正确匹配形式
bool isoperand(char symb);//判断是否为操作数
bool prcd(char symb1,char symb2);//比较优先级
void postfix(char inStr[],char postStr[]);//将前缀表达式转化成后缀表达式
double counter(char postStr[]);//对后缀表达式运算
double oper(char symb,double op1,double op2);//对两个操作数进行symb运算
double get_number(char num_str[],int length,int);//将数字字符串转化成double型
int main()
{
char inStr[50],postStr[50];
double result;
int choice;
cout<<"请输入运算表达式(注意末尾不要输入'='号)"<<endl;
do
{
gets(inStr);
postfix( inStr, postStr);
if(!judge_of_inStr(inStr))
{
cout<<"表达式错误，括号不匹配"<<endl;
exit(1);
}
result= counter(postStr);
cout<<"计算结果为: "<<result<<endl;
cout<<"继续计算请输入1，退出请输入0"<<endl;
cin>>choice;
cout<<"-------------------------------------------------------"<<endl;
}while(choice==1);
return 0;
}
bool empty(num_stack*p)//判断操作数栈是否为空
{
return (p->top==-1);
}
bool empty(opert*p)//判断操作数栈是否为空
{
return (p->top==-1);
}
void PopAndTest(num_stack*p,double *x,bool*test)//....
{
if(empty(p))
*test=true;
else
{
*test=false;
*x=p->a[p->top];
p->top--;
}
}
void PopAndTest(opert*p,char *x,bool*test)//如果为空，返回ture
{
if(empty(p))
*test=true;
else
{
*test=false;
*x=p->a[p->top];
p->top--;
}
}
void PushAndTest(num_stack*p,double x,bool*test)//.....
{
if(p->top==StackSize-1)
*test=true;
else
{
*test=false;
p->top++;
p->a[p->top]=x;
}
}
void PushAndTest(opert*p,char x,bool*test)
{
if(p->top==StackSize-1)
*test=true;
else
{
*test=false;
p->top++;
p->a[p->top]=x;
}
}
char pop(opert*p)
{
if(p->top==-1)
{
cout<<"表达式格式错误!"<<endl;
exit(1);
}
else
return p->a[p->top--];
}
double pop(num_stack*p)
{
if(p->top==-1)
{
cout<<"表达式格式错误!"<<endl;
exit(1);
}
else
return p->a[p->top--];
}
void push(opert*p,char symb)
{
if(p->top==StackSize-1)
{
cout<<"表达式格式错误!"<<endl;
exit(1);
}
p->a[++p->top]=symb;
}
void push(num_stack*p,double num)
{
if(p->top==StackSize-1)
{
cout<<"表达式格式错误!"<<endl;
exit(1);
}
p->a[++p->top]=num;
}
bool isoperand(char symb) //判断是否是操作数
{
return (symb>='0'&&symb<='9');
}
bool prcd(char symb1,char symb2)//比较两个操作符的优先级
{
int former,later;
char precedence[10][10]=
{
{'>','>','<','<','<','>','<','<'},
{'>','>','<','<','<','>','<','<'},
{'>','>','>','>','<','>','<','<'},
{'>','>','>','>','<','>','<','<'},
{'<','<','<','<','<','<','<','<'},
{'0'},
{'>','>','>','>','<','>','<','<'},
{'>','>','>','>','<','>','>','0'}
};
switch(symb1)
{
case '+':former=0;break;
case '-':former=1;break;
case '*':former=2;break;
case '/':former=3;break;
case '(':former=4;break;
case ')':former=5;break;
case '^':former=6;break;
case '~':former=7;break;
default:
cout<<"操作符错误!"<<endl;
exit(1);
}
switch(symb2)
{
case '+':later=0;break;
case '-':later=1;break;
case '*':later=2;break;
case '/':later=3;break;
case '(':later=4;break;
case ')':later=5;break;
case '^':later=6;break;
case '~':later=7;break;//......
default:
cout<<"操作符错误!"<<endl;
exit(1);
}
return (precedence[former][later]=='>');
}
void postfix(char inStr[],char postStr[])//把前缀表达式转化成后缀表达式
{
int i=0;
int j=0;
bool test;
char topsymb='+';
char symb;
opert*p;
p=new opert;
p->top=-1;
if(inStr[0]=='-')
inStr[0]='~';
while((symb=inStr[i])!='\0')
{
if(isoperand(symb))
{
while((isoperand(symb)&&symb!='\0')||symb=='.')
{
postStr[j++]=symb;
symb=inStr[++i];
}
postStr[j++]='#';
}
else
{
if(symb=='-'&&inStr[i-1]=='(')
symb='~';
PopAndTest(p,&topsymb,&test);
while(!test&&prcd(topsymb,symb))
{
postStr[j++]=topsymb;
PopAndTest(p,&topsymb,&test);
}
if(!test)
push(p,topsymb);
if(test||symb!=')')
push(p,symb);
else
topsymb=pop(p);
i++;
}
}
while(!empty(p))
postStr[j++]=pop(p);
postStr[j]='\0';
printf("后缀表达式：");
printf("%s ['#'代表空格]\n",postStr);
}
double oper(char symb,double op1,double op2)
{
switch(symb)
{
case '+': return (op1+op2);break;
case '-':return (op1-op2);break;
case '*':return (op1*op2);break;
case '/':
if(op2!=0)
{
return (op1/op2);
}
else
printf("表达式不合法!\n");
exit(1);
break;
case '^':
if(op1==0 && op2==0)
{
printf("表达式不合法!\n");
exit(1);
}
else
return pow(op1,op2);
break;
default:
{
cout<<"无"<<symb<<"操作,错误在oper中"<<endl;
exit(1);
}
}
}
double get_number(char num_str[],int length,int position_of_point)
{
double sum=0;
int i;
for(i=0;i<length;i++)
{
if(num_str[i]=='.')
{
position_of_point++;
continue;
}
sum+=(num_str[i]-'0')*pow(10,position_of_point-i-1);
}
return sum;
}
double counter(char postStr[])
{
double op1,op2;
double value;
char symb;
char num_str[20];//可能越界
int iOFnum_str=0;
bool exist_point;
int k,position_of_point,i=0;
num_stack*p;
p=new num_stack;
p->top=-1;
symb=postStr[i];
while(symb!='\0')
{
iOFnum_str=0;
k=0;
exist_point=false;
while(isoperand(symb)||symb=='.')
{
if(symb=='.')
{
position_of_point=k;
exist_point=true;
}
k++;
num_str[iOFnum_str]=symb;
iOFnum_str++;
symb=postStr[++i];
}
if( exist_point==false)
{
position_of_point=k;
}
if(symb=='#')
push(p,get_number(num_str,k,position_of_point));
else if(symb=='~')
{
op1=pop(p);
push(p,-op1);
}
else
{
op2=pop(p);
op1=pop(p);
value=oper(symb,op1,op2);
push(p,value);
}
i++;
symb=postStr[i];
}
return pop(p);
}
bool judge_of_inStr(char a[])//
{
char symb,topsymb;
int i=0;
opert*p;
bool test;
p=new opert;
p->top=-1;
symb=a[i];
while(symb!='\0')
//for(symb=a[i];symb!='\0';i++)
{
if(symb=='(')
push(p,symb);
if(symb==')')
{
PopAndTest(p,&topsymb,&test);
if(test)
return false;
}
i++;
symb=a[i];
}
return empty(p);
}
