数据结构 算术表达式求值 C++ 栈方法

//算术表达式求值 //作者：金航 #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; }