#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <cmath>
using namespace std;
bool IsOperator(string mystring)
//判断字符串是否是运算符
{
if(mystring == "-"||mystring == "+"||mystring == "*"||mystring == "/")
return true;
else
return false;
}
bool IsOperator(char ops)
//判断一个字符是否是运算符
{
if(ops == '+'||ops== '-'||ops== '*'||ops== '/'||ops=='('||ops==')')
return true;
else
return false;
}
bool IsOperand(char ch)
//判断是否是数字
{
if (((ch>='0')&&(ch<='9'))||(ch=='.'))
return true;
else
return false;
}
bool judge(string exp)
//判断输入是否正确
{
char check;
int error=0,lb=0,rb=0,numofoperand=0,numofoperator=0;
for(int m=0;m<exp.size();m++)
{
check=exp[m];
if(IsOperand(check))
{
if(check=='.')//判断浮点型数据是否正确
{
if(!(exp[m-1]>='0'&&exp[m-1]<='9')&&(exp[m+1]>='0'&&exp[m+1]<='9'))
{
error++;
cout<<"浮点型数据输入有误!!!"<<endl;
}
}
numofoperand++;
}
else if(IsOperator(check))
{
if(check==')')
{
rb++;
if(rb>lb)
{
error++;
cout<<"右括号不可能大于左括号!!!"<<endl;
}
if(IsOperator(exp[m+1])&&(exp[m+1]=='+'||exp[m+1]=='-'||exp[m+1]=='*'||exp[m+1]=='/'||exp[m+1]==')'))
{
numofoperator++;
m++;
if(exp[m]==')')
rb++;
}
else if(IsOperator(exp[m+1])||IsOperand(exp[m+1]))
{
error++;
cout<<"右括号后不可能直接跟数据或左括号!!!"<<endl;
}
}
else if(check=='(')
{
lb++;
if(IsOperator(exp[m+1])&&exp[m+1]=='('||exp[m+1]=='-')//左括号右边只能是数字或者"-"号
{
m++;
m++;
lb++;
}
else if(IsOperator(exp[m+1]))
{
error++;
cout<<"左括号后运算符只能跟左括号!!!"<<endl;
}
}
else
{
numofoperator++;
if(IsOperator(exp[m+1])&&exp[m+1]=='(')
{
m++;
lb++;
}
else if(IsOperator(exp[m+1]))
{
error++;
cout<<"非括号的运算符不能直接接非括号运算符!!!"<<endl;
}
}
}
else
{
error++;
cout<<check<<"为非法字符!!!"<<endl;
}
}
if((error==0)&&(lb==rb)&&(numofoperand!=0)&&(numofoperator!=0))
return true;
else
return false;
}
bool
addition(char
OperatorA,char
OperatorB)
//A和B的优先级相同时返回TRUE.
{
if(OperatorA==OperatorB||(OperatorA=='*'&&OperatorB=='/')||(OperatorA=='/'&&OperatorB=='*')||(OperatorA=='+'&&OperatorB=='-')||(OperatorA=='-'&&OperatorB=='+'))
return
true;
else
return
false;
}
bool TakesPrecedence(char OperatorA,char OperatorB)
//按照优先级用if从最优至最后从上至下排列，从而达到比较A与B的优先级
{
if(OperatorA=='(')
return false;
else if(OperatorB=='(')
return false;
else if(OperatorB==')')
return true;
else
if(addition(OperatorA,OperatorB))
return false;
else if((OperatorA=='*')||(OperatorA=='/'))
return true;
else if((OperatorB=='*')||(OperatorB=='/'))
return false;
else
if((OperatorA=='+')||(OperatorA=='-'))
return
true;
else
return true;
}
//****************************************************************************//
class BinNode{
public:
string data;
BinNode *left_child;
BinNode *right_child;
BinNode(string k)
//构造函数
{
data=k;
left_child=NULL;
right_child=NULL;
}
};
class binarytree//树的类
{
public:
BinNode *root;
//根节点
binarytree(void){root=NULL;}
//构造函数
void print(void){print(root);}
void print(BinNode *p)
{
if(p!=NULL)
{
print(p->left_child);
print(p->right_child);
cout<<p->data<<" ";
}
}
void evaluate(void){evaluate(root);}
bool evaluate(BinNode *prt)
//计算二叉树一个节点
{
if(IsOperator(prt->data)&&!IsOperator(prt->left_child->data)&&!IsOperator(prt->right_child->data))//计算二叉树结点的值并存入新的二叉树结点
{
float num=0;
float num1=atof(prt->left_child->data.c_str());
float num2=atof(prt->right_child->data.c_str());
if(prt->data=="+")
num=num1+num2;
else if(prt->data=="-")
num=num1-num2;
else if(prt->data=="*")
num=num1*num2;
else if(prt->data=="/")
{
if(num2==0.0)
{
cout<<"除数为零!!!运算出错";
return 0;
}
else
num=num1/num2;
}
stringstream bob;
bob<<num;
string suzzy(bob.str());
prt->data=suzzy;
prt->left_child=NULL;
prt->right_child=NULL;
}
else if(prt->left_child==NULL&&prt->right_child==NULL);
else
{
evaluate(prt->left_child);
evaluate(prt->right_child);
evaluate(prt);
}
return 1;
}
void clear_help(void)
{
clear_help(root);
}
void clear_help(BinNode *rt)
{
if(rt!=NULL)
{
clear_help(rt->left_child);
clear_help(rt->right_child);
delete rt;
}
}
};
BinNode *build_node(string x)//创建一个临时结点
{
BinNode *new_node;
new_node=new BinNode(x);
return (new_node);
}
void copy(BinNode *&r1,BinNode* r2)//这里将单个的子树连接起来
{
if(r2==NULL)
r1=NULL;
else
{
r1=build_node(r2->data);
copy(r1->left_child,r2->left_child);
copy(r1->right_child,r2->right_child);
}
}
//*******************************************************************************************
int main()
{
binarytree etree;//创建树
stack<binarytree> NodeStack;//创建栈
stack<char> OpStack;
string exp;//声明字符串
char choice='y';//choice为选择是否继续运行程序的判断
char c;//为下面创建二叉树进行取字符
while(choice=='y'||choice=='Y')
{
cout<<"请输入一个有效的表达式:"<<endl;
getline(cin,exp);
cout<<"
"<<endl<<"-----------------------------"<<endl;
if(judge(exp))//如果判断出表达式没有错误，则进行创建二叉树并计算
{
cout<<"表达式格式正确"<<endl;
for(int i=0;i<exp.size();i++)
{
c=exp[i];
if(i==0 && c=='-') //若开始为负，则把零压入运算数栈，把'-'压入运算符栈
{
binarytree
temp;
temp.root=build_node("0");
NodeStack.push(temp);
OpStack.push('-');
}
else
if(IsOperand(c))//若是操作数，则判断下一位是不是操作数，并且将整个数据创建一个子树并压栈
{
string tempstring="";
tempstring=tempstring+c;
while(i+1<exp.size()&&IsOperand(exp[i+1]))
//当当前位置的下一位也是操作数时，将整个数字放在一个临时数据串中
{
tempstring+=exp[++i];
}
binarytree temp;//为这个数据创建一个子树
temp.root=build_node(tempstring);
NodeStack.push(temp);//将子树的根节点指针压栈
}
else if(c=='+'||c=='-'||c=='/'||c=='*')//如果是操作符
{
if(OpStack.empty())//如果栈空，则直接压栈
OpStack.push(c);
else if(OpStack.top()=='(')//如果栈顶是左括号，则压栈
OpStack.push(c);
else if(TakesPrecedence(c,OpStack.top()))//判断栈顶字符和当前字符的优先级，当c优先级高或者个优先级相同时，将c压栈
OpStack.push(c);
else//其他普通情况
{
while(!OpStack.empty()&&(TakesPrecedence(OpStack.top(),c)||addition(OpStack.top(),c)))//这里将在一般情况下，对已经压栈的操作数和操作符进行创建子树处理，并将当前字符压栈
{
binarytree temp_tree;
string thisstring="";
thisstring=thisstring+OpStack.top();//取栈顶进行计算字符串
OpStack.pop();
etree.root=build_node(thisstring);//当前树的根为栈顶计算出的字符串
copy(temp_tree.root,NodeStack.top().root);//子树的根节点放在临时树结点上
NodeStack.pop();
etree.root->right_child=temp_tree.root;//将临时结点放入新建子树的右孩子结点上，可以将个子树连接起来
temp_tree.root=NULL;//置空临时树结点
copy(temp_tree.root,NodeStack.top().root);//重复上面的步骤连接左孩子
etree.root->left_child=temp_tree.root;
NodeStack.pop();
temp_tree.root=NULL;
copy(temp_tree.root,etree.root);
NodeStack.push(temp_tree);
etree.root=NULL;
}
OpStack.push(c);
}
}
else if(c=='(')
//若中间遇到括号，则判断下一位是否为'-'
{
OpStack.push(c);
if(exp[i+1]=='-')
{
binarytree
temp;
temp.root=build_node("0");
NodeStack.push(temp);
OpStack.push('-');
i++;
}
}
else if(c==')')//如果遇到右括号，则创建子树，直到与左括号匹配成功，这里和前一步骤的操作基本相同
{
while(OpStack.top()!='(')
{
binarytree temp_tree;
string thisstring="";
thisstring=thisstring+OpStack.top();
OpStack.pop();
etree.root=build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child=temp_tree.root;
temp_tree.root=NULL;
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child=temp_tree.root;
NodeStack.pop();
temp_tree.root=NULL;
copy(temp_tree.root,etree.root);
NodeStack.push(temp_tree);
etree.root=NULL;
}
OpStack.pop();
}
}
while(!OpStack.empty())//如果栈非空，则继续进行出栈、判断、计算，直到栈空，栈中的结果为最终的计算结果
{
binarytree temp_tree;
string thisstring="";
thisstring=thisstring+OpStack.top();
OpStack.pop();
etree.root=build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child=temp_tree.root;
temp_tree.root=NULL;
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child=temp_tree.root;
NodeStack.pop();
temp_tree.root=NULL;
copy(temp_tree.root,etree.root);
NodeStack.push(temp_tree);
if(!OpStack.empty())
etree.root=NULL;
}
//cout<<"Postfix traversal:";
//etree.print();
//cout<<endl;
etree.evaluate();
cout<<"表达式计算结果:"<<exp<<"="<<etree.root->data<<endl;
cout<<"------------------------------------------------"<<endl;
cout<<endl<<"是否继续计算下一个表达式<y/n>:";
cin>>choice;
getchar();
}
else
{
cout<<"**************************"<<endl;
cout<<"错误：表达式有误"<<endl;
cout<<endl<<"是否继续计算下一个表达式<y/n>:";
cin>>choice;
getchar();
}
}
return 0;
}
2006-12-06 14:52
