2 基于栈的中缀算术表达式求值
实验要求:(1)运算符包括+、-、*、/、(、)、=
(2)参加运算的数为double类型且为正数
(3)表达式以‘=’结尾
实现方法：建两个栈，OPTR和OPND，书上算法3.22可作参考，但它只考虑了个位数的运算，需创建一个字符数组存放输入进的数字，从而达到“拼数”的效果，然后借用atof()函数实现将string转化为double型的数。
代码：
#include <iostream> #include <stdlib.h> #include <cstring> #include<iomanip>//该头文件为了后面的输出保留两位小数 #define MAXSIZE 100//初始分配的存储空间 #define OK 1 #define OVERFLOW -2 #define ERROR -1 using namespace std; //定义字符栈 typedef struct { char* base; char* top; int stackSize; } SqStackOPTR; //定义数字栈 typedef struct { double* base; double* top; int stackSize; } SqStackOPND; //字符栈的初始化 int InitStack(SqStackOPTR& S) { S.base = new char[MAXSIZE]; if (!S.base) exit(OVERFLOW); S.top = S.base; S.stackSize = MAXSIZE; return OK; } //数字栈的初始化 int InitStack(SqStackOPND& S) { S.base = new double[MAXSIZE]; if (!S.base) exit(OVERFLOW); S.top = S.base; S.stackSize = MAXSIZE; return OK; } //字符栈入栈操作 int Push(SqStackOPTR& S, char e) { if (S.top - S.base == MAXSIZE) return ERROR; *S.top++ = e;//元素e进栈 return OK; } //数字栈入栈操作 int Push(SqStackOPND& S, double e) { if (S.top - S.base == MAXSIZE) //说明栈满 return ERROR; *S.top++ = e;//元素e进栈 return OK; } //字符栈出栈操作 char Pop(SqStackOPTR& S) { char e; if (S.top == S.base) return ERROR; e = *--S.top; return e; } //数字栈出栈操作 double Pop(SqStackOPND& S) { double e; if (S.top == S.base) return ERROR; e = *--S.top; return e; } //取字符栈栈顶元素 char GetTop(SqStackOPTR S) { char e; if (S.top == S.base) return ERROR; e = *(S.top - 1); return e; } //取数字栈栈顶元素 double GetTop(SqStackOPND S) { double e; if (S.top == S.base) return ERROR; e = *(S.top - 1); return e; } //判断字符的方法，判断输入的字符是数字还是运算符 //如果是数字，那么返回0，如果是运算符，返回1 int In(char ch) { int isNumber; switch (ch) { case '+': case '-': case '*': case '/': case '(': case ')': case '=': isNumber = 1; break; default: isNumber = 0; break; } return isNumber; } //定义一个判定运算符栈的栈顶元素与读入的运算符之间优先关系的函数 char Precede(char top, char ch) {//top为栈顶元素，ch为读入的字符 char sym; switch (top) { case '+': case '-': switch (ch) { case '+': case '-': case ')': case '=': sym = '>'; break; case '*': case '/': case '(': sym = '<'; break; } break; case '*': case '/': switch (ch) { case '+': case '-': case '*': case '/': case ')': case '=': sym = '>'; break; case '(': sym = '<'; break; }break; case '(': switch (ch) { case '+': case '-': case '*': case '/': case '(':sym = '<'; break; case ')': sym = '='; break; }break; case ')': switch (ch) { case '+': case '-': case '*': case '/': case ')': case '=':sym = '>'; break; }break; case '=': switch (ch) { case '+': case '-': case '*': case '/': case '(':sym = '<'; break; case '=': sym = '='; break; } break; } return sym; } //定义一个二元运算的方法 double Operate(double a, char top, double b) { double sum = 0; switch (top) { case '+': sum = a + b; break; case '-':sum = a - b; break; case '*': sum = a * b; break; case '/':sum = a / b; break; } return sum; } double EvaluateExpression(char ch) { SqStackOPTR OPTR;//定义字符栈 SqStackOPND OPND;//定义数字栈 InitStack(OPTR);//初始化OPTR栈 InitStack(OPND);//初始化OPND栈 Push(OPTR, '=');//将表达式起始符’=‘压入OPTR栈 char chs[20];//定义一个字符数组，来实现数字转换为字符串 memset(chs, '#', sizeof(char) * 20);//将字符数组的元素设置为‘#’,即初始化chs数组，不然会报错 while (ch != '=' || GetTop(OPTR) != '=') {//表达式没有扫描完毕或OPTR的栈顶元素不为“=” if (!In(ch)) { //这里应该将字符串转换为数字 for (int i = 0; i < strlen(chs); i++) { if (chs[i] == '#' && !In(ch)) {//如果数组的第i个元素不为‘#’或不为符号 chs[i] = ch; cin >> ch; } else { break; } } double d = atof(chs);//把字符串转换成浮点数 double Push(OPND, d); memset(chs, '#', sizeof(char) * 20);//将字符数组的元素设置为‘#’ } else { switch (Precede(GetTop(OPTR), ch)) { case '<': Push(OPTR, ch); cin >> ch; break; case '>': char theta; double b; double a; theta = Pop(OPTR); b = Pop(OPND); a = Pop(OPND); double sum; sum = Operate(a, theta, b); Push(OPND, sum); break; case '=': Pop(OPTR); cin >> ch; break; } } } return GetTop(OPND); } int main() { while (1) { char ch; cin >> ch; if (ch == '=')break; double res = EvaluateExpression(ch); cout << fixed << setprecision(2) << res << endl;//输出保留两位小数 } return 0; }运行结果
（第二个表达式的括号为中文的括号，结果很奇怪）
心得：
要注意字符和字符串的初始化，不然总是报错，vs其实有时候也反应不过来。
第一次接触memset()函数，atof()函数。
