說明:
采用樹形結構處理表達式,按優先級運算結果,壹個加,減,乘,除或數值為壹個節點
優先級如下:
函數:4
括號:3
乘除:2
加減:1
*/
#include <windows.h>
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
using namespace std;
const char NUM[]={'0','1','2','3','4','5','6','7','8','9','.'};
const char OPERATION[]={'+','-','*','/'};
const double PI=3.14159265358979;
const double EE=2.71828182818281;
class Fun //處理系統數學函數的類
{
public:
Fun(string o,int t,double l=0.0,double r=0.0):op(o),type(t),lvalue(l),rvalue(r){}
static string FUN[];
double calc();
private:
int type; //666 0 1 sin90 2 3! 3 3C2
string op; //函數類型
double lvalue; //函數左邊的值
double rvalue; //函數右邊的值
static int FunNum;
};
int Fun::FunNum=10;
string Fun::FUN[]={"!","sin","cos","tan","log","ln","C","A","^","-"};
/*
函數說明:
1:log是以10為底的工程對數
2:ln 是以e為底的自然對數
3:C 計算組合數 輸入規則 如計算 3取2的組合 輸入表達式 3C2
4:A 計算排列數 輸入規則 如計算 3取2的排列 輸入表達式 3A2
5:! 計算階乘
6:^ x的y次方 輸入 x^y
*/
int factorial(int n) //階乘函數
{
int i,s=1;
for(i=1;i<=n;i++)
s*=i;
return s;
}
int C(int a,int b)
{
return factorial(a)/(factorial(b)*factorial(a-b));
}
int A(int a,int b)
{
return factorial(a)/factorial(b);
}
double Fun::calc() //計算系統函數的值
{
if(type==0)
return lvalue;
else
{
if(op=="!")
return factorial(lvalue);
if(op=="sin")
return sin(rvalue/180*PI);
if(op=="cos")
return cos(rvalue/180*PI);
if(op=="tan")
return tan(rvalue/180*PI);
if(op=="log")
return log10(rvalue);
if(op=="ln")
return log10(rvalue)/log10(EE);
if(op=="C")
return C(lvalue,rvalue);
if(op=="A")
return A(lvalue,rvalue);
if(op=="^")
return pow(lvalue,rvalue);
if(op=="-")
return -rvalue;
else
{
string err="暫時沒有函數"+op;
MessageBox(NULL,err.c_str(),"錯誤",MB_OK);
return 0;
}
}
}
struct Unit //雙向鏈表保存運算單元
{
Unit(int p,char o,string c,double v,int t,Unit * pr=NULL,Unit * n=NULL)
:PRI(p),Operation(o),Code(c),value(v),Type(t),Pre(pr),Next(n){}
int PRI; //優先級
char Operation; //操作符
string Code; //原始代碼
double value; //數據
int Type; //類型 操作符0 數據1 函數2
Unit * Pre; //構成雙向鏈表
Unit * Next;
};
class Node //表達式樹狀結構的節點
{
public:
Node(char o,int p,int e=1,double v=0,Node * ph=NULL,Node * pl=NULL,Node * pr=NULL)
:Operation(o),PRI(p),Expression(e),value(v),Head(ph),Left(pl),Right(pr){}
Node * Head; //節點的根,左樹枝,右樹枝
Node * Left;
Node * Right;
double GetValue();
char GetOperation() const {return Operation;}
int GetPri() const {return PRI;}
int IsExp() const {return Expression;}
private:
char Operation; //操作符
int PRI; //優先級
int Expression; //記錄該節點是否是表達式0 1
double value; //該節點的值
};
double Node::GetValue() //運算該節點的值
{
if(IsExp()) //該節點的值還未算出來
{
double lvalue,rvalue;
lvalue=Left->GetValue();
rvalue=Right->GetValue();
Expression=0;
char op=GetOperation();
switch(op)
{
case '+':
return lvalue+rvalue;
case '-':
return lvalue-rvalue;
case '*':
return lvalue*rvalue;
case '/':
return lvalue/rvalue;
default:
return 0;
}
}
else
return value;
}
bool Isnum(char c)
{
for(int i=0;i<sizeof(NUM);i++)
{
if(c==NUM[i])
return true;
}
return false;
}
bool Isoperation(char c)
{
for(int i=0;i<sizeof(OPERATION);i++)
{
if(c==OPERATION[i])
return true;
}
return false;
}
Unit * Analyse(string exp) //分析表達式並生成鏈表
{
int pri=0; //當前優先級
int stat=1; //當前的讀入狀態 括號 0 運算符 1 其他 2
Unit * head=NULL,* p=NULL;
int i=0,explen;
explen=exp.size();
for(i=0;i<explen;i++)
{
char c=exp.at(i);
if(c=='(')
{
pri+=3;
stat=0;
}
else if(c==')')
{
pri-=3;
stat=0;
}
else if(Isoperation(c) && stat!=1) //操作符後的當正負號處理
{
stat=1;
Unit * temp=p;
int add_pri; //自身增加的優先級
if(c=='+' || c=='-')
add_pri=1;
else
add_pri=2;
p->Next=new Unit(pri+add_pri,c," ",0,0);
p=p->Next;
p->Pre=temp;
}
else //其他的當做函數處理
{
stat=2;
string function="";
while(i<explen && (c=exp.at(i),! Isoperation(c)) && c!=')')
{
function+=c;
i++;
}
i--;
if(head==NULL)
{
p=new Unit(pri,' ',function,0,2);
head=p;
}
else
{
Unit * temp=p;
p->Next=new Unit(pri,' ',function,0,2);
p=p->Next;
p->Pre=temp;
}
}
}
return head;
}
Unit * Calc(Unit * head) //計算雙向鏈表基本單元的值
{
Unit * p=head;
while(p!=NULL)
{
if(p->Type!=0) //非操作符
{
string temp=p->Code;
string op;
double lvalue=0,rvalue=0;
int l_point=0,r_point=0;
int i=0,type=0;
char ch;
while(i<temp.size() && (ch=temp.at(i),Isnum(ch)))
{
if(ch=='.')
{
l_point++;
i++;
continue;
}
if(! l_point)
lvalue*=10;
lvalue+=(ch-'0')*pow(10,-l_point);
i++;
if(l_point)
l_point++;
}
while(i<temp.size() && (ch=temp.at(i),! Isnum(ch)))
{
op+=ch;
type=1;
i++;
}
while(i<temp.size() && (ch=temp.at(i),Isnum(ch)))
{
if(ch=='.')
{
r_point++;
i++;
continue;
}
if(! r_point)
rvalue*=10;
rvalue+=(ch-'0')*pow(10,-r_point);
i++;
if(r_point)
r_point++;
}
Fun * f=new Fun(op,type,lvalue,rvalue);
p->value=f->calc();
}
p=p->Next;
}
return head;
}
Node * Tree(Unit * head) //生成表達式樹
{
Node * root=NULL,* proot=NULL,* pbranch=NULL;
Unit * p=head;
int now_pri; //當前優先級
bool hadop=false;
while(p!=NULL)
{
if(p->Type==0) //如果是壹個操作符
{
hadop=true;
if(root==NULL)
{
proot=new Node(p->Operation,p->PRI,1);
root=proot;
pbranch=root;
now_pri=p->PRI;
proot->Left=new Node(' ',0,0,p->Pre->value);
proot->Right=new Node(' ',0,0,p->Next->value);
}
else
{
if(p->PRI<now_pri) //優先級低於當前優先級,樹根方向
{
proot=new Node(p->Operation,p->PRI,1); //新的樹根
proot->Left=root; //根的變換
proot->Left->Head=proot;
proot->Right=new Node(' ',0,0,p->Next->value);
proot->Right->Head=proot;
root=proot;
pbranch=proot; //右樹枝的變換
//pbranch->Right=new Node(' ',0,0,p->Pre->value); //樹枝右邊取值
}
else if(p->PRI==now_pri) //優先級相同,先算左邊的
{
Node * temp;
temp=new Node(p->Operation,p->PRI,1);
temp->Left=pbranch;
if(pbranch->Head==NULL)
{
proot=temp;
root=proot;
pbranch->Head=proot;
}
else
{
Node * temp0;
temp0=pbranch->Head;
temp0->Right=temp;
temp->Head=temp0;
pbranch->Head=temp;
}
pbranch=temp;
pbranch->Right=new Node(' ',0,0,p->Next->value);
pbranch->Right->Head=pbranch;
}
else
{
Node * temp;
temp=new Node(p->Operation,p->PRI,1);
pbranch->Right=temp;
temp->Head=pbranch;
pbranch=pbranch->Right;
pbranch->Left=new Node(' ',0,0,p->Pre->value);
pbranch->Left->Head=pbranch;
pbranch->Right=new Node(' ',0,0,p->Next->value);
pbranch->Right->Head=pbranch;
}
now_pri=p->PRI;
}
}
p=p->Next;
}
if(! hadop)
root=new Node(' ',0,0,head->value);
return root;
}
int main()
{
string exp;
ifstream infile("test.txt",ios::in);
while(! getline(infile,exp).eof())
{
if(exp=="")
continue;
Unit * h=Analyse(exp);
h=Calc(h);
Node * root=Tree(h);
cout<<exp<<"="<<root->GetValue()<<endl;
}
return 0;
}