//算术表达式求值
//作者：金航
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <conio.h>
#include "SqStack.h"
using namespace std;
char input[1024];
SqStack<double> OPND;
SqStack<char> OPTR;
int count = 0;
Status InitProcess();
bool CheckExpress();
int JudgeOptr(char ch);
#define UNACCEPTED 0
#define NUMBER 1
#define POINT 2
#define OPERATOR 3
#define BRAC 4
#define SHARP 5
void Message(int pos, int type, const char *words);
#define INFO 0
#define ERROR 1
#define WORNING 2
#define YES 1
#define NO 0
Status ParseToFloat(char* &p, double &ret);
#define EXTRAPOINT 1
#define POINTATNUMHEAD 2
char Precede(char theta1, char theta2);
double Operate(double num1, char theta, double num2);
void Print(char *p);
int main()
{
char *p = NULL;
char numtmp[16];
int state = OK, rtn;
cout << "算术表达式求值\n"
<< "表达式条件限制：\n"
<< "最大长度1024，以'#'结束，每个数字不超过15位(小数点算1位)\n"
<< "请输入表达式(输入首字符为'#'时退出程序)：";
MAINLOOP:
while (true)
{
state = OK;
count = 0;
if (ERROR == InitProcess()) //初始化
{
Message(0, ERROR, "初始化失败。");
}
p = &input[0];
count++;
if (input[0] == '#') //首个字符为#时退出程序
{
break;
}
if (!CheckExpress()) //检查表达式
{
continue;
}
while ('#' != *p || '#' != OPTR.GetTop()) //表达式处理过程
{
if (NUMBER == JudgeOptr(*p) || POINT == JudgeOptr(*p))
{
double num;
if (*(p - 1) == ')')
{
Message(count, ERROR, "语法错误，计算中止");
goto ENDDING;
}
rtn = ParseToFloat(p, num);
if (EXTRAPOINT == rtn)
{
Message(count, ERROR, "同个数中小数点超过1个");
goto ENDDING;
}
else if (POINTATNUMHEAD == rtn)
{
Message(count, ERROR, "小数点位于数字开头");
goto ENDDING;
}
else
{
OPND.Push(num);
Print(p);
}
}
else
{
if ('(' == *p && NUMBER == JudgeOptr(*(p - 1)))
{
OPTR.Push('*');
Print(p);
}
switch (Precede(OPTR.GetTop(), *p))
{
case '<':
if (ERROR == OPTR.Push(*p))
{
Message(count, ERROR, "语法错误，数字和括号关系有误，计算中止");
goto ENDDING;
}
p++;
count++;
Print(p);
break;
case '=':
if (ERROR == OPTR.Pop())
{
Message(count, ERROR, "语法错误，计算中止");
goto ENDDING;
}
p++;
count++;
Print(p);
break;
case '>':
char opr;
double topa, topb, rst;
state = OK;
state += OPTR.Pop(opr);
state += OPND.Pop(topb);
state += OPND.Pop(topa);
Print(p);
if (state > OK)
{
Message(count, ERROR, "语法错误，运算数不足，计算中止");
goto ENDDING;
}
rst = Operate(topa, opr, topb);
OPND.Push(rst);
Print(p);
break;
case '*':
Message(count, ERROR, "语法错误，计算中止");
goto ENDDING;
break;
default:
break;
}
}
}
cout << "Input:#" << input << endl
<< "表达式已接受。\n"
<< "计算值：" << OPND.GetTop();
ENDDING:
cin.clear();
cin.sync();
}//MainLoop
return 0;
}
void Print(char *p)
{
cout << "String: " << p << endl;
cout << "OPTR: ";
OPTR.ShowAllStack();
cout << "OPND: ";
OPND.ShowAllStack();
cout << "----------------\n";
}
Status InitProcess()
{
count = 0;
cout << "\n\n#";
cin.getline(input, 1024, '\n');
OPTR.DestoryStack();
OPND.DestoryStack();
if (OK == OPTR.InitStack()
&& OK == OPND.InitStack())
{
OPTR.Push('#');
return OK;
}
return ERROR;
}
bool CheckExpress()
{
char *p;
int pos = 0, replace = 0;
//检查以'#'结束
if (input[strlen(input) - 1] != '#')
{
Message(strlen(input) + 1, ERROR, "没有以'#'结束。");
return false;
}
//替换中大括号为小括号
cout << ' ';
for (p = &input[0]; *p != '#'; p++)
{
switch (*p)
{
case '{':
case '[':
cout << '^';
*p = '(';
replace++;
break;
case '}':
case ']':
cout << '^';
*p = ')';
replace++;
break;
default:
cout << ' ';
break;
}
}
cout << endl;
if (replace > 0)
{
cout << "提示：有" << replace << "处括号将被替换为圆括号。\n";
}
//检查非法字符
for (p=&input[0]; *p!='#'; p++)
{
if (UNACCEPTED == JudgeOptr(*p))
{
Message(pos + 1, ERROR, "含有非法字符。");
return false;
}
pos++;
}
return true;
}
int JudgeOptr(char ch)
{
int chnum;
char accept[] = {'1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
'.', '+', '-', '*', '/', '(', ')', '#'};
for (chnum = 0; chnum < 18; chnum++)
{
if (ch == accept[chnum])
{
break;
}
}
if (chnum < 10)
{
return NUMBER;
}
else
{
switch (chnum)
{
case 10:
return POINT;
break;
case 11: case 12: case 13: case 14:
return OPERATOR;
break;
case 15: case 16:
return BRAC;
break;
case 17:
return SHARP;
break;
default:
return UNACCEPTED;
break;
}
}
}
void Message(int pos, int type, const char *words)
{
cout << "Input: \n#" << input << endl;
for (int i=0; i<pos; i++)
{
cout << ' ';
}
cout << '^' << "\n位置" << pos << "：";
switch (type)
{
case INFO:
cout << "提示：" << words << endl;
break;
case ERROR:
cout << "错误：" << words << endl;
cin.clear();
cin.sync();
break;
case WORNING:
cout << "警告：" << words << endl;
break;
default:
break;
}
return;
}
Status ParseToFloat(char* &p, double &ret)
{
char numstr[12];
int i;
bool point = false;
memset(numstr, 0, sizeof(numstr));
if (*p == '.')
{
ret = 0.0f;
return POINTATNUMHEAD;
}
for (i = 0; JudgeOptr(*p) < 3; i++)
{
numstr[i] = *p;
if (*p == '.')
{
if (point)
{
ret = 0.0f;
return EXTRAPOINT;
}
else
{
point = true;
}
}
p++;
count++;
}
numstr[i] = '\0';
ret = atof(numstr);
return OK;
}
char Precede(char theta1, char theta2)
{ // +-*/()#
char table[7][8] = {">><<<>>", //+
">><<<>>", //-
">>>><>>", //*
">>>><>>", ///
"<<<<<=*", //(
">>>>*>>", //)
"<<<<<*="}; //#
char order[] = "+-*/()#";
int x, y;
for (int i=0; i<7; i++)
{
if (order[i] == theta1)
{
y = i;
}
if (order[i] == theta2)
{
x = i;
}
}
return table[y][x];
}
double Operate(double num1, char theta, double num2)
{
double ret = 0.0f;
switch (theta)
{
case '+':
ret = num1 + num2;
break;
case '-':
ret = num1 - num2;
break;
case '*':
ret = num1 * num2;
break;
case '/':
ret = num1 / num2;
break;
default:
break;
}
return ret;
}
