数据结构计算器.doc

#include<stdio.h>
#include<iostream>
#include<string>
#include<stack>
#include<map>
#include<stdlib.h>
#include<cstring>
using namespace std;
char nifix_expre[200];//存放中缀表达式
string suffix_expre;//后缀表达式,最后转换成const char*
map<string,double>string_num;//用于将表达式中各个数字映射成单个字符+'\0'
map<char,int>out;//外部优先级
map<char,int>in;//内部优先级
stack<char>operation;
stack<string>num;
stack<string>temp;
char op[7]={'+','-','*','/','#','(','('};
string snum[11]={"a","b","c","d","e","f","g","h","i","j","k"};

bool isnotoperation(char a)
{
if(a=='+'||a=='-'||a=='*'||a=='/'||a=='#'||a=='('||a==')')
return false;
return true;
}
void prechange(char *a)
{
int j=0;
int length=strlen(a);
// cout<<i;
string new_nifix;
/*
for(int i=0;i<length;i++)
{
if((*(a+i)=='+'||*(a+i)=='-'||*(a+i)=='*'||*(a+i)=='/')&&*(a+i+1)=='-')
{
for(int j=length;j>i+1;j--)
{
*(a+j)=*(a+j-1);
}
*(a+i+1)='0';
length++;
}
}
cout<<a<<endl;
*/
for(int i=0;i<length;i++)
{
string anum;
while(isnotoperation(*(a+i)))
{
anum+=*(a+i);
i++;
}
string kk;
if(strlen(anum.c_str()))
{
double bnum=atof(anum.c_str());
string_num[snum[j]]=bnum;
kk=snum[j++];
}
new_nifix=new_nifix+kk+*(a+i);
}
//测试输出处理的数字
cout<<new_nifix<<endl;

map<string,double>::iterator it=string_num.begin();
for(;it!=string_num.end();it++)
cout<<it->first<<" "<<it->second<<endl;
strcpy(a,new_nifix.c_str());
}
void change(char *a)
{
int n=strlen(a);
for(int i=0;i<n;i++)
{
if(isnotoperation(*(a+i)))
{
string kk;
kk+=*(a+i);
num.push(kk);
// cout<<" shuzi "<<kk<<endl;
}
else
{
if(operation.empty())
operation.push(*(a+i));
else
{
if(out[*(a+i)]>in[operation.top()])
operation.push(*(a+i));
else if(out[*(a+i)]==in[operation.top()])
{

operation.pop();
}
else if(out[*(a+i)]<in[operation.top()])
{
while(out[*(a+i)]<in[operation.top()])//此处切记切记加循环！！！
{
char temp_oper=operation.top();
operation.pop();
string kk;
kk+=temp_oper;
temp.push(kk);

for(int m=0;m<2;m++)
{
kk=num.top();
num.pop();
temp.push(kk);
}
kk=temp.top();
temp.pop();
for(int m=0;m<2;m++)
{
kk+=temp.top();
temp.pop();
}
num.push(kk);
// cout<<kk<<endl;
}

if(out[*(a+i)]==in[operation.top()])//这里一定要比较弹出相等的等号
{
// cout<<operation.top()<<endl;
operation.pop();

}
else
{
operation.push(*(a+i));
}

}
}
}
}
suffix_expre=num.top();
cout<<suffix_expre<<endl;
}
double caclu(double a,double b,char c)
{
switch(c)
{
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':
if(b==0)
{
cout<<"youwu"<<endl;
return -500000;
}
else
return a/b;
}
}
double cacluate(string bb)
{
stack<double>last;
char end[200];
strcpy(end,bb.c_str());
// cout<<end<<endl;
for(int i=0;i<strlen(end);i++)
{
if(isnotoperation(*(end+i)))
{
string kk;
kk+=*(end+i);
double aa=string_num[kk];
last.push(aa);

}
else
{
double b=last.top();
last.pop();
double a=last.top();
last.pop();
double result=caclu(a,b,*(end+i));
if(result==-500000)
return -500000;
last.push(result);

}
}
return last.top();
}
int main()
{
string begin;

while(cin>>begin)
{
begin='#'+begin+'#';
strcpy(nifix_expre,begin.c_str());
// cin>>nifix_expre;

prechange(nifix_expre);
// cout<<nifix_expre<<endl;
in['#']=out['#']=0;
in['(']=out[')']=1;
in[')']=out['(']=8;
in['*']=in['/']=5;
in['+']=in['-']=3;
out['*']=out['/']=4;
out['+']=out['-']=2;
change(nifix_expre);
if(cacluate(suffix_expre)!=-500000)
cout<<cacluate(suffix_expre)<<endl;
}

}