之前写到一半因为其他事情耽搁了，导致时间跨度有好几个月，今天总算是写完了
先附题目：读入一个非负整数表达式，只含有+-*/运算符。数字和运算符之间都有一个空格。
#include"iostream"
#include"istream"
#include"string"
#include"stack"
#include<stdio.h>
using namespace std;
void getNext(int &i, double &retnu, bool &retop);
string str;
stack<double> nu; //数字栈
stack<int> op; //运算符栈
int mat[][5] = { {1,0,0,0,0 } ,//mat[i][j]==0 表示i的优先级小于j的优先级 否则高于
{ 1,0,0,0,0 },
{ 1,1,0,0,0 },
{ 1,1,1,0,0 },
{ 1,1,1,1,0 } };
void getNext(int &i, double &retnu, bool &retop)
{
if (str[i] >= '0'&&str[i] <= '9')
{
//截取出数字
double a;
a = str[i] - '0';
for (i++; str[i] >= '0'&&str[i] <= '9'; i++)
{
double b = str[i] - '0';
a *= 10;
a += b;
}
retop = false;
retnu = a;
i++;
//i--; 不用i-- 因为for里的最后一个i++刚好跳过空格
}
else { //为运算符 用retnu返回运算符代码编号
retop = true;
if (str[i] == '#')
{
retnu = 0;
}
if (str[i] == '+')
{
retnu = 1;
}
if (str[i] == '-')
{
retnu = 2;
}
if (str[i] == '*')
{
retnu = 3;
}
if (str[i] == '/')
{
retnu = 4;
}
i += 2;//跳过自身和其后的空格
}
}
int main()
{
//1.读入字符串
//string str1;
getline(cin,str);
//string str2 = "#";
// str = str2 + str1 + str2;
//gets_s(str);
//str = "4 + 2 * 5";
str = str + ' ' + '#';
str.insert(0, "# ");
cout << str << endl;
//cout << "str[i]>='0' str[i]<='9'" << '0' << " " << '9' << "str[2]" << str[2] << endl;
//2.建立两个堆栈
//3.建立运算符优先级
//#_0 +_1 -_2 *_3 /_4
//4.读取字符串进行计算
int i = 0;
while (true)
{
//读取下一个元素 若为数字则由retnu纪录 retop==false 若为运算符 则由retnu纪录其代码 retop==true
//用变量i指向当前遍历到的元素
int temp_i = i;//I在调用getNext(）后就会移到下一个元素的位置 所以这里纪录一下i的位置
double retnu = -1;
bool retop = true;
cout << "getNext(i,retnu,retop);" << i << " " << retnu << " " << retop << endl;
getNext(i, retnu, retop);//函数也要实现对i的移动
cout << "AFTER;" << i << " " << retnu << " " << retop << endl;
if (retop == false)//若为数字 进入数字栈
{
cout << retnu << "入数字栈" << endl;
nu.push(retnu);
}
else if (retop = true)//若为运算符
{
if (op.empty() == true || mat[(int)retnu][op.top()] == 1)//运算符栈为空或i优先级高于栈顶运算符优先级 则入栈
{
cout << "op.empty() == true " << op.empty() << " mat[(int)retnu][op.top()] == 1" << endl;
cout << retnu << "入运算符栈" << endl;
op.push((int)retnu);
}
else {
while (mat[(int)retnu][op.top()] == 0)//i优先级低与栈顶运算符则循环计算栈顶运算直到不满足此条件
{
double a1;
a1 = nu.top();
nu.pop();
double a2;
a2 = nu.top();
nu.pop();
int op1 = op.top();
op.pop();
cout << "计算" << a2 << " " << a1 << "运算代号为" << op1 << endl;
if (op1 == 1)
{
a2 = a2 + a1;
}
if (op1 == 2)
{
a2 = a2 - a1;
}
if (op1 == 3)
{
a2 = a2*a1;
}
if (op1 == 4)
{
a2 = a2 / a1;
}
nu.push(a2);
cout << "temp_i " << temp_i << " op.pop() " << op.top() << endl;
}
// cout << retnu << "入运算符栈" << endl;
op.push((int)retnu);
}
}
//结束条件
if (op.size() == 2 && op.top() == 0) //运算符栈只有两个元素 且栈顶元素为#所对应的编码 则结束遍历
{
break;
}
}
//5.输出结果
cout << "结果为：" << nu.top() << endl;
getchar(); getchar(); getchar();
return 0;
}
总结一下写的过程和遇到的问题：
刚开始写的时候先把别人的代码照着打了一遍，打完之后发现对具体过程任然不是很理解，然后就去仔细的都程序的算法，也就是解决此题的思路。
把大致的思路了解之后就自己尝试去写，这就开始对细节进行考虑去怎么实现。
第一个问题就是怎么去遍历输入的字符串，刚开始采用的for语句来一个一个的读入字符，但后来发现当数字是两位以上时就会产生另一个问题，即for读取字符会把两位以上的数字分开，这时发现读取的单位不可以是一个字符而要是一个完整的元素，这个元素可以是一个数字，也可以是一个运算符，于是就采用了一个函数来实现读取一个元素的功能。
第二个问题就是运算符优先级。优先级采用了数组的方式来进行存储。其中遇到的一个问题就是当运算符是同一个的时候，如遍历到#，而且运算符栈里也是#，此时判定优先级应该怎么办？分析发现此时应该设置为遍历的#优先级应该大于栈顶的#，否则的话就会使得遍历的#号一直无法入运算符栈从而产生错误。
第三个问题就是对字符串的操作。
首尾要添加了#来最后用于字符串遍历的结束，那么这要怎么添加呢？我的思路是采用了string的+和insert()函数来分别对输入字符串的尾部和首部进行添加#，其中insert()函数是string提供的在指定位置插入字符串，所以其参数是str和要插入的位置。
还有一个遇到的问题就是用vc2015遇到的如图的错误是数组越界的原因。
还有要注意的一点是在早期写的时候由于过程有些地方不清楚而写错的地方，比如参数调用错了，在后期调试的过程中花了很长时间才改正过来。
附本题算法：
1.设立两个堆栈，一个用来保存运算符，另一个用来保存数字。
2在表达式首尾添加标记运算符，改运算符优先级最低。
3从左至右依次遍历字符串，若遍历到到运算符，则将其与运算符栈栈顶元素进行比较，若运算符栈顶元素优先级小于改运算符，则将改运算符入栈，遍历下一个元素。
4若运算符栈顶运算符优先级大于改运算符，则弹出该运算符，在从数字栈取出数字进行运算，结果返回到数字栈中，循环比较直至运算符栈顶运算符小于该运算符的优先级，此时改运算符入栈。
5若为数字则直接进入数字栈
6若运算符栈只有两个元素，且栈顶为添加的标记运算符，则结束运算，数字栈里的唯一数字即为表达式的答案。
声明：内容包括王道论坛计算机考研的题目和内容。