简单的表达式求值
一直很想做个比Windows自带的高级一点的计算器，能将整个表达式输入，然后求值。
这个程序要求读者具备编译原理的一些知识。
举个实例来说明程序处理过程。假设要求值的表达式为 -25*（56+15）#(其中＃号作为表达式结束标志)。首先对表达式进行词法分析，允许出现的字符为{0 ，1， 2 ，3 ，4 ，5 ，6， 7 ，8， 9 . ，+ ，-， *， / ，（ ，），＃}分析的结果产生两种类型的单词：操作符和操作数。操作符包括：{+, - ,* ,/ ,（ ,）}操作数包括int和double类型。上面表达式产生的单词序列为{-25,*,(,56,+,15,)}.这些单词的类型也需要保存。
词法分析正确后将对产生的单词序列进行语法分析。
定义E为表达式，N为常数（视为终结符）。表达式的产生式可表示如下：
E à N
E à (E)
E à E+E
E à E-E
E à E*E
E à E/E
消除左递归后的产生式(E_为新产生的符号):
E->NE_
E->(E)E_
E_->+EE_
E_->-EE_
E_->*EE_
E_->/EE_
E_->NULL (空串)
可以根据这个产生式构造递归的语法分析器。具体细节就不叙述了，可以阅读源代码。
语法分析正确后就可以求值了，求值时用到一个操作数堆栈和操作符堆栈，以及一个算符优先表（存储了运算符之间的优先关系），具体细节可以阅读源码。
/*stack.h*/
template
class CStack
{
public:
CStack()
{
Head = new Node;
Head->Next = NULL;
}
void Push(T data)
{
Node* tem;
tem = Head->Next;
Head->Next = new Node;
Head->Next->Next = tem;
Head->Next->Data = data;
}
BOOL Pop(T& data)
{
if(Head->Next)
{
data = Head->Next->Data;
Node* tem = Head->Next->Next;
delete Head->Next;
Head->Next = tem;
return TRUE;
}
else
return FALSE;
}
BOOL GetTop(T& data)
{
if(Head->Next)
{
data = Head->Next->Data;
return TRUE;
}
return FALSE;
}
virtual ~CStack()
{
Node* pNode = Head;
Node* tem;
while(pNode)
{
tem = pNode->Next;
delete pNode;
pNode = tem;
}
}
protected:
struct Node
{
T Data;
Node* Next;
};
Node* Head;
};
class PriorityTable
{
int** pTable;
int TableSize;
public:
PriorityTable()
{
int i,j;
pTable =NULL;
TableSize = 7;
pTable = new int* [TableSize];
for( i = 0; i < TableSize; i++)
pTable[i] = new int[TableSize];
for( i = 0; i < TableSize; i++)
for( j = 0; j
pTable[i][j] = 1;
pTable[4][5] = pTable[6][6] = 0;
pTable[0][2] = pTable[0][3] = pTable[0][4] = -1;
pTable[1][2] = pTable[1][3] = pTable[1][4] = -1;
pTable[2][4] = -1;
pTable[3][4] = -1;
for( j = 0; j < 5; j++)
pTable[4][j] = -1;
for( j = 0; j < 5; j++)
pTable[6][j] = -1;
}
~PriorityTable()
{
for(int i=0; i< TableSize ; i++)
{
delete []pTable[i];
}
delete []pTable;
}
int CharToIndex(char ch)
{
switch (ch)
{
case '+':
return 0;
case '-':
return 1;
case '*':
return 2;
case '/':
return 3;
case '(':
return 4;
case ')':
return 5;
case '#':
return 6;
default:
return -1;
}
}
int Compare(const char FirstOper,const char SecondOper)
{
int FirstIndex = CharToIndex(FirstOper);
int SecondIndex = CharToIndex(SecondOper);
if(FirstIndex != -1 && SecondIndex != -1 )
return pTable[FirstIndex][SecondIndex];
return -2;
}
int Compare(int x,int y)
{
if( x>=0 && x=0 && y
return pTable[x][y];
return -2;
}
};
// ForTest.cpp : Defines the entry point for the console application.
//
#define MaxWordNum 100
#define MaxWordLength 100
class WordAnalyse
{
protected:
char Words[MaxWordNum][MaxWordLength];
int WordsAttribute[MaxWordNum];
int CurrentWordNum;
char* pCurrentLocation ;
char* pLastLocation;
bool bResult;
bool WordType;
char Expression[100];
public:
WordAnalyse(char* chExpression)
{
int i,j;
for(i = 0; i
{
for(j = 0; j Words[i][j] = '\0';
WordsAttribute[i] = 0;
}
CurrentWordNum = 0;
pCurrentLocation = NULL;
strcpy(Expression,"(");
strcat(Expression,chExpression);
pCurrentLocation = Expression+1;
pLastLocation = Expression;
bResult = WordsAnalyse();
WordType = IsAllDouble();
}
int GetWordNum()
{
return CurrentWordNum;
}
char* GetWord(int index)
{
if(index>=CurrentWordNum)
return NULL;
else
return Words[index];
}
int GetWordAttribute(int index)
{
if(index>=CurrentWordNum)
return -100;
return WordsAttribute[index];
}
bool GetResult()
{
return bResult ;
}
bool TypeIsDouble()
{
return WordType;
}
protected:
bool IsAllDouble()
{
for(int i = 0;i
{
if(WordsAttribute[i] == 1 || !strcmp(Words[i],"/"))
return true;
}
return false;
}
bool WordsAnalyse()
{
while(*pCurrentLocation != '\0')
if(!GenerateWord())
return false;
return true;
}
bool IsNumber(char ch)
{
if(ch >= '0' && ch <= '9')
return true;
return false;
}
bool GenerateWord()
{
if(*pCurrentLocation == ' ')
do
{
pCurrentLocation++;
}
while(*pCurrentLocation == ' ');
switch(*pCurrentLocation)
{
case '+':
case '*':
case '/':
case '(':
case ')':
case '#':
Words[CurrentWordNum][0] = *pCurrentLocation;
WordsAttribute[CurrentWordNum] = 2;
CurrentWordNum++;
pLastLocation = pCurrentLocation;
pCurrentLocation++;
return true;
case '-':
if(*pLastLocation != '(') // - 号为双目操作符
{
Words[CurrentWordNum][0] =
*pCurrentLocation;
WordsAttribute[CurrentWordNum] = 2;
}
else //－为单目操作符
{
Words[CurrentWordNum][0] = '0';
WordsAttribute[CurrentWordNum] = 0;
CurrentWordNum++;
Words[CurrentWordNum][0] = '-';
WordsAttribute[CurrentWordNum] = 2;
}
CurrentWordNum++;
pLastLocation = pCurrentLocation;
pCurrentLocation++;
return true;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
int i ;
i = 0;
do
{
Words[CurrentWordNum][i++] =
*pCurrentLocation;
pLastLocation = pCurrentLocation;
pCurrentLocation++;
}while(IsNumber(*pCurrentLocation));
if(*pCurrentLocation == '.')
{
Words[CurrentWordNum][i++] =
*pCurrentLocation;
pCurrentLocation++;
if(!IsNumber(*pCurrentLocation))
return false;
while(IsNumber(*pCurrentLocation))
{
Words[CurrentWordNum][i++] =
*pCurrentLocation;
pLastLocation = pCurrentLocation;
pCurrentLocation++;
}
WordsAttribute[CurrentWordNum] = 1;
CurrentWordNum ++;
return true;
}
else
{
CurrentWordNum ++;
return true;
}
default :
return false;
}
return false;
}
};
#include "WordAnalyse.h"
class SyntaxAnalyse
{
bool bResult;
int WordIndex;
public:
SyntaxAnalyse() {bResult = true; WordIndex = 0;}
bool Analyse(WordAnalyse* pWords);
protected:
void E(WordAnalyse* pWords);
void E_(WordAnalyse* pWords);
// void N(WordAnalyse* pWords);
};
bool SyntaxAnalyse::Analyse(WordAnalyse* pWords)
{
if(pWords->GetResult() == false)
return false;
E(pWords);
if( WordIndex < pWords->GetWordNum() - 1)
{
bResult = true;
WordIndex = 0;
return false;
}
bool tem = bResult;
bResult = true;
WordIndex = 0;
return tem;
}
void SyntaxAnalyse::E(WordAnalyse* pWords)
{
if(strcmp(pWords->GetWord(WordIndex),"(") == 0)
{
WordIndex++;
E(pWords);
if(strcmp(pWords->GetWord(WordIndex),")") == 0)
{
WordIndex++;
E_(pWords);
}
else
{
bResult = false;
return;
}
}
else
if(pWords->GetWordAttribute(WordIndex) != 2)
{
WordIndex++;
E_(pWords);
}
else
{
bResult = false;
return;
}
}
void SyntaxAnalyse::E_(WordAnalyse* pWords)
{
//char tem[100] = "\0";
// strcpy(tem,Words.GetWord(WordIndex));
// char Operator = tem[0];
if(strcmp(pWords->GetWord(WordIndex),"+") == 0 ||
strcmp(pWords->GetWord(WordIndex),"-") == 0 ||
strcmp(pWords->GetWord(WordIndex),"*") == 0 ||
strcmp(pWords->GetWord(WordIndex),"/") == 0
)
{
WordIndex++;
E(pWords);
E_(pWords);
}
else
return;
}
#include "stack.h"
#include "CompareTable.h"
#include "SyntaxAnalyse.h"
class CalExpression
{
public:
CalExpression(char* Expression);
int GetValueType();
int GetIntResult();
double GetDoubleResult();
bool GetResult();
int Calculate();
protected:
int Operate(char Operator,int Fir,int Sec);
double Operate(char Operator,double Fir,double Sec);
protected:
PriorityTable MyTable;
WordAnalyse MyWords;
SyntaxAnalyse MySyntax;
protected:
bool bResult;
int nResult;
double dResult;
int ValueType;
};
CalExpression::CalExpression(char* Expression):MyWords(Expression)
{
bResult = false;
nResult = 0;
dResult = 0;
ValueType = -1;
}
bool CalExpression::GetResult()
{
return bResult;
}
int CalExpression::GetValueType()
{
return ValueType;
}
int CalExpression::Operate(char Operator,int Fir,int Sec)
{
switch (Operator)
{
case '+':
return Fir+Sec;
case '-':
return Fir - Sec;
case '*':
return Fir * Sec;
case '/':
return Fir/Sec;
}
return 0;
}
double CalExpression::Operate(char Operator,double Fir,double Sec)
{
switch (Operator)
{
case '+':
return Fir+Sec;
case '-':
return Fir - Sec;
case '*':
return Fir * Sec;
case '/':
return Fir/Sec;
}
return 0;
}
int CalExpression::GetIntResult()
{
return nResult;
}
double CalExpression::GetDoubleResult()
{
return dResult;
}
int CalExpression::Calculate()
{
bResult = false;
nResult = 0;
dResult = 0;
ValueType = -1;
if(!MySyntax.Analyse(&MyWords))
return ValueType = -1;
if(MyWords.TypeIsDouble())
{
CStack CharStack;
CStack ValueStack;
CharStack.Push('#');
int WordIndex = 0;
char top;
CharStack.GetTop(top);
while(!(strcmp(MyWords.GetWord(WordIndex),"#") == 0 && top ==
'#'))
{
if(MyWords.GetWordAttribute(WordIndex) != 2)
{
double Value = atof(MyWords.GetWord(WordIndex));
ValueStack.Push(Value);
WordIndex ++;
}
else
{
switch (MyTable.Compare(top,(MyWords.GetWord
(WordIndex))[0]))
{
case -1:
CharStack.Push((MyWords.GetWord
(WordIndex))[0]);
WordIndex ++;
break;
case 0:
CharStack.Pop(top);
WordIndex ++;
break;
case 1:
{
double nFirNum ,nSecNum, nResult;
char Operator;
ValueStack.Pop(nSecNum);
ValueStack.Pop(nFirNum);
CharStack.Pop(Operator);
nResult = Operate
(Operator,nFirNum,nSecNum);
ValueStack.Push(nResult);
break;
}
default :
break;
}
}
CharStack.GetTop(top);
}
ValueStack.GetTop(dResult );
ValueType = 1;
return 1;
}
else
{
CStack CharStack;
CStack ValueStack;
CharStack.Push('#');
int WordIndex = 0;
char top;
CharStack.GetTop(top);
while(!(strcmp(MyWords.GetWord(WordIndex),"#") == 0 && top ==
'#'))
{
if(MyWords.GetWordAttribute(WordIndex) != 2)
{
int Value = atoi(MyWords.GetWord(WordIndex));
ValueStack.Push(Value);
WordIndex ++;
}
else
{
switch (MyTable.Compare(top,(MyWords.GetWord
(WordIndex))[0]))
{
case -1:
CharStack.Push((MyWords.GetWord
(WordIndex))[0]);
WordIndex ++;
break;
case 0:
CharStack.Pop(top);
WordIndex ++;
break;
case 1:
{
int nFirNum ,nSecNum,nResult;
char Operator;
ValueStack.Pop(nSecNum);
ValueStack.Pop(nFirNum);
CharStack.Pop(Operator);
nResult = Operate
(Operator,nFirNum,nSecNum);
ValueStack.Push(nResult);
break;
}
default :
break;
}
}
CharStack.GetTop(top);
}
ValueStack.GetTop(nResult );
ValueType = 0;
return 0;
}
}
