怎么解析一个数学表达式 - Chinaunix

#include <stdio.h>
enum ElemType
{
Type_Number = 0,
Type_Root,
Type_Plus,
Type_Subtract,
Type_Prior,
Type_Multiply,
Type_Divide,
};
class CCalcElem
{
public:
CCalcElem() : m_iType(Type_Number) {}
~CCalcElem()
{
if (m_iType != Type_Number)
{
delete m_lpLeft;
delete m_lpRight;
}
}
protected:
CCalcElem(const CCalcElem&) {}
const CCalcElem& operator=(const CCalcElem&) { return *this; }
public:
int m_iType;
union {
double m_dlNumber;
struct {
CCalcElem* m_lpLeft;
CCalcElem* m_lpRight;
};
};
CCalcElem* m_lpParent;
};
static bool IsBlank(char ch)
{
return ((ch == ' ') || (ch == '\t') || (ch == '\r') || (ch == '\n'));
}
int AnalyseNumber(const char*& lpExpress, CCalcElem* lpTree);
static int AnalyseOperator(const char*& lpExpress, CCalcElem* lpTree)
{
while (IsBlank(*lpExpress))
++lpExpress;
int iType;
switch (*lpExpress)
{
case '+':
iType = Type_Plus;
break;
case '-':
iType = Type_Subtract;
break;
case '*':
iType = Type_Multiply;
break;
case '/':
iType = Type_Divide;
break;
case ')':
++lpExpress;
return 1;
case '\0':
return 0;
default:
return -1;
}
++lpExpress;
CCalcElem* lpNode = lpTree->m_lpParent;
if (iType < Type_Prior)
{
if (lpNode->m_iType != Type_Root)
{
lpNode = lpNode->m_lpParent;
if (lpNode->m_iType != Type_Root)
lpNode = lpNode->m_lpParent;
}
}
else
{
if ((lpNode->m_iType != Type_Root) && (lpNode->m_iType > Type_Prior))
lpNode = lpNode->m_lpParent;
}
CCalcElem* const lpElem = new CCalcElem;
lpElem->m_lpParent = lpNode;
CCalcElem* const lpNodeRight = lpNode->m_lpRight;
lpNode->m_lpRight = lpElem;
lpElem->m_iType = iType;
lpElem->m_lpLeft = lpNodeRight;
lpElem->m_lpRight = NULL;
return AnalyseNumber(lpExpress, lpElem);
}
int AnalyseNumber(const char*& lpExpress, CCalcElem* lpTree)
{
while (IsBlank(*lpExpress))
++lpExpress;
if (*lpExpress == '(')
{
++lpExpress;
const int iType = lpTree->m_iType;
lpTree->m_iType = Type_Root;
const int iResult = AnalyseNumber(lpExpress, lpTree);
if (iResult > 0)
{
lpTree->m_iType = iType;
return AnalyseOperator(lpExpress, lpTree->m_lpRight);
}
}
else
{
double dl;
int count;
if (sscanf(lpExpress, "%lf%n", &dl, &count) > 0)
{
lpTree->m_lpRight = new CCalcElem;
lpTree->m_lpRight->m_lpParent = lpTree;
lpTree->m_lpRight->m_dlNumber = dl;
lpExpress += count;
return AnalyseOperator(lpExpress, lpTree->m_lpRight);
}
}
return -1;
}
static double CalcTree(CCalcElem* lpTree)
{
if (lpTree->m_iType != Type_Number)
{
const double dlLeft = CalcTree(lpTree->m_lpLeft);
const double dlRight = CalcTree(lpTree->m_lpRight);
const int iType = lpTree->m_iType;
if (iType == Type_Plus)
return (dlLeft + dlRight);
else if (iType == Type_Subtract)
return (dlLeft - dlRight);
else if (iType == Type_Multiply)
return (dlLeft * dlRight);
else
return (dlLeft / dlRight);
}
return lpTree->m_dlNumber;
}
static bool AnalyseExpress(const char* lpExpress, double& dlValue)
{
CCalcElem nElem;
nElem.m_iType = Type_Root;
nElem.m_lpLeft = NULL;
nElem.m_lpRight = NULL;
if (AnalyseNumber(lpExpress, &nElem) == 0)
{
dlValue = CalcTree(nElem.m_lpRight);
return true;
}
return false;
}
int main(int, char**)
{
printf("%s", "Input expression:");
char str[512];
gets(str);
double dlResult;
if (AnalyseExpress(str, dlResult))
printf("%s = %lf\r\n", str, dlResult);
else
printf("%s", "Invalid expression!\r\n");
return 0;
}

复制代码