1、问题分析和任务定义、
【问题描述】
设计一个简单的算术表达式计算器。
【基本要求】
实现标准整数类型的四则运算表达式的求值（包含括号，可多层嵌入）.
【测试数据】
(30+2*70)/3-12*3
5+(9*(62-37)+15)*6
要求自行设计非法表达式，进行程序测试，以保证程序的稳定运行。
【实现提示】
可以设计以下辅助函数
status isNumber（char ReadInChar）； //视ReadInchar 是否是数字而返回 TRUE 或 FALSE 。
int TurnToInteger（char IntChar)； // 将字符’0’.’9’ 转换为整数 9
2、数据结构的选择和概要设计
数据结构选择：
选择的是栈，分为操作数栈，储存数字如1，2，3；以及运算符栈如（[{#。
概要设计：
流程图
3、详细设计和编码
#includeusing namespace std; typedef struct SNode1//运算符栈链 { char data; struct SNode1* next; }StackNode1, * Linkstack1; typedef struct SNode2//数字栈链 { int data; struct SNode2* next; }StackNode2, * Linkstack2; void InitStack1(Linkstack1& S)//初始化运算符栈链 { S = NULL; } void InitStack2(Linkstack2& S)//初始化数字栈链 { S = NULL; } void push1(Linkstack1& S, char ch)//运算符入栈 { Linkstack1 p; p = (Linkstack1)malloc(sizeof(Linkstack1)); p->data = ch; p->next = S; S = p; } void push2(Linkstack2& S, int ch)//数字入栈 { Linkstack2 p; p = (Linkstack2)malloc(sizeof(Linkstack2)); p->data = ch; p->next = S; S = p; } char GetTop1(Linkstack1& S)//获得运算符栈栈顶元素 { if (S != NULL) return S->data; } int GetTop2(Linkstack2& S)//获得数字符栈栈顶元素 { if (S != NULL) return S->data; } void pop1(Linkstack1& S, char& e)//用元素e存储当前运算符栈栈顶元素 { //弹出栈顶元素,栈顶指针指向下一元素 e = GetTop1(S); if (S != NULL) { S = S->next; } } void pop2(Linkstack2& S, int& e)//用元素e存储当前数字栈栈顶元素 { //弹出栈顶元素,栈顶指针指向下一元素 e = GetTop2(S); if (S != NULL) { S = S->next; } } int In(char ch)//In函数检测字符ch是运算符还是数字 { //若为运算符，返回1；若为数字，返回0 switch (ch) { case '(':return 1; case ')':return 1; case '+':return 1; case '-':return 1; case '*':return 1; case '/':return 1; case '#':return 1; case '[':return 1; case ']':return 1; case '{':return 1; case '}':return 1; default: return 0; } } char Precede(char a, char b)//比较运算符优先级 { if (b == '+') { if (a == '(' || a == '#' || a == '[' || a == '{') return '<'; return '>'; } if (b == '-') { if (a == '(' || a == '#' || a == '[' || a == '{') return '<'; return '>'; } if (b == '*') { if (a == '*' || a == '/' || a == ')' || a == ']' || a == '}') return '>'; return '<'; } if (b == '/') { if (a == '*' || a == '/' || a == ')' || a == ']' || a == '}') return '>'; return '<'; } if (b == '(') return '<'; if (b == ')') { if (a == '(') return '='; return '>'; } if (b == '#') { if (a == '#') return '='; return '>'; } if (b == '[') { if (a == ')') return '>'; return '<'; } if (b == ']') { if (a == '[') return '='; return '>'; } if (b == '{') { if (a == ')' || a == ']') return '>'; return '<'; } if (b == '}') { if (a == '{') return '='; return '>'; } } int Operate(int a, char op, int b)//根据运算符，进行运算 { switch (op) { case '+':return a + b; break; case '-':return a - b; break; case '*':return a * b; break; case '/':return a / b; break; } } void Cout_stack1(Linkstack1& S)//输出运算符栈元素 { Linkstack1 T; T = new StackNode1; T = S; if (T == NULL) { cout << "运算符栈为空！！"; } while (T) { cout << T->data << 't'; T = T->next; } cout << endl; }void Cout_stack2(Linkstack2& S)//输出字符栈元素 { Linkstack2 T; T = new StackNode2; T = S; if (T == NULL) { cout << "操作数栈为空！！"; } while (T) { cout << T->data << 't'; T = T->next; } cout << endl; } int EvaluateExpression() { char theta = 0, x = 0; int a = 0, b = 0; Linkstack1 OPTR;//运算符 Linkstack2 OPND;//操作数 Linkstack1 q; InitStack1(OPTR); InitStack2(OPND); InitStack1(q); cout << "请输入算术表达式（英文键盘输入）："; push1(OPTR, '#'); char ch; cin >> ch; cout << "……………………………………………………" << endl; if (ch == ')' || ch == ']' || ch == '}' || ch == '+' || ch == '-' || ch == '*' || ch == '/') { cout << "输入错误！！！表达式第一个值不能为运算符" << endl; cout << "……………………………………………………" << endl; cout << endl; cin.ignore(100, 'n'); return 77777; } cout << "初始运算符栈:"; Cout_stack1(OPTR); cout << "初始操作数栈:"; Cout_stack2(OPND); cout << "……………………………………………………" << endl; while (ch != '#' || GetTop1(OPTR) != '#') { //cout << "输入序列:" << ch << endl; q = OPTR; if (ch != '#' && ch != '0' && ch != '1' && ch != '2' && ch != '3' && ch != '4' && ch != '5' && ch != '6' && ch != '7' && ch != '8' && ch != '9' && ch != '+' && ch != '-' && ch != '*' && ch != '/' && ch != '(' && ch != ')' && ch != '[' && ch != ']' && ch != '{' && ch != '}') { cout << "错误！！！非法输入！！！！" << endl; cout << "……………………………………………………" << endl; cout << endl; cin.ignore(100, 'n'); return 77777; }//检测非法输入 if (ch == ')') { while (q->data != '(' && q->next) { q = q->next; } if (q->data != '(') { cout << "错误！！！右小括号输入过多！！！" << endl; cout << "……………………………………………………" << endl; cout << endl; cin.ignore(100, 'n'); return 77777; } }//括号匹配 if (ch == ']') { while (q->data != '[' && q->next) { q = q->next; } if (q->data != '[') { cout << "错误！！！右中括号输入过多！！！" << endl; cout << "……………………………………………………" << endl; cout << endl; cin.ignore(100, 'n'); return 77777; } }//括号匹配 if (ch == '}') { while (q->data != '{' && q->next) { q = q->next; } if (q->data != '{') { cout << "错误！！！右大括号输入过多！！！" << endl; cout << "……………………………………………………" << endl; cout << endl; cin.ignore(100, 'n'); return 77777; } }//括号匹配 if (!In(ch))//In函数检测字符ch是运算符还是数字 { //若为运算符，返回1；若为数字，返回0 int q = 0; q = ch - 48; int temp, temp1; push2(OPND, q); cin >> ch; //cout << "输入序列:" << ch << endl; for (int i = 0; i < 99; i++) { if (ch >= 48 && ch <= 57) { int l = ch - 48; pop2(OPND, temp); temp1 = temp * 10 + l; push2(OPND, temp1); cin >> ch; //cout << "输入序列:" << ch << endl; } } } else { switch (Precede(GetTop1(OPTR), ch))//运算符优先级比较 { case'<':push1(OPTR, ch); cin >> ch; break; case'>': pop1(OPTR, theta); pop2(OPND, b); if (OPND == NULL) { cout << "错误！！！运算符过多！！！" << endl; cout << "……………………………………………………" << endl; cout << endl; cin.ignore(100, 'n'); return 77777; }//检测运算符是否过多 pop2(OPND, a); push2(OPND, Operate(a, theta, b)); break; case'=':pop1(OPTR, x); cin >> ch; break; } } if (ch == '#') { if (q->data == '(') { q = q->next; if (q->data == '(') { cout << "错误！！！左小括号输入过多！！！" << endl; cout << "……………………………………………………" << endl; cout << endl; cin.ignore(100, 'n'); return 77777; } } }//括号匹配 if (ch == '#') { if (q->data == '[') { q = q->next; if (q->data == '[') { cout << "错误！！！左中括号输入过多！！！" << endl; cout << "……………………………………………………" << endl; cout << endl; cin.ignore(100, 'n'); return 77777; } } }//括号匹配 if (ch == '#') { if (q->data == '{') { q = q->next; if (q->data == '{') { cout << "错误！！！左大括号输入过多！！！" << endl; cout << "……………………………………………………" << endl; cout << endl; cin.ignore(100, 'n'); return 77777; } } }//括号匹配 cout << "运算符栈:"; Cout_stack1(OPTR); cout << "操作数栈:"; Cout_stack2(OPND); cout << "……………………………………………………" << endl; } cout << "运算符栈:"; Cout_stack1(OPTR); cout << "操作数栈:"; Cout_stack2(OPND); cout << "……………………………………………………" << endl; return GetTop2(OPND); } int main() { for (int i = 0; i < 40; i++) { cout << "欢迎使用算术表达式计算器！！" << endl; cout << "注意：输入结束时请用#符号结束，否则将使程序崩溃！！！！" << endl; int a = EvaluateExpression(); if (a != 77777) { cout << "运算结果为：" << a << endl; cout << "……………………………………………………" << endl; cout << endl; } } }
4、测试结果及其分析
(30+2*70)/3-12*3测试，其结果为20
5+(9*(62-37)+15)*6的测试结果为1445
5、用户使用说明
注意，输入的算数表达式必须合法，不能出现中文小括号以及其他非法符号，再表达式的末尾必须要加上#，防止系统崩溃。
