2017《面向对象程序设计》课程作业五
031602230 卢恺翔
Github传送门
题目叙述
- 本次作业要求将程序写成.cpp和.h分离的形式
- 根据设计的类图进行编码，搭建主体框架
- 本次作业不要求实现核心的算法功能
- 发表一篇博客，博客内容为：提供本次作业的github链接，对栈的知识学习探索
由于已经完成了程序.cpp和.h的分离形式，并按照类进行了编码，所以就不在这里详叙了，详见2017《面向对象程序设计》课程作业四和GitHub链接
对栈的知识学习探索
栈是一种特殊的线性表，遵循lifo（last in first out)的原则，只能在栈的最顶端（即栈顶）进行删除和插入操作。栈顶由一个top指针指向，当向栈插入一个元素的时候，top指针会从栈顶再向上移动一位，从而让插入的元素进入栈并成为栈顶元素。如果是出栈，则top指针向下移动一位，则相当于原来的栈顶元素被移除（即出栈）。栈的大部分操作都是有top指针来完成的。
在C++中，可以通过
#include<stack>
来直接定义并使用栈。例如
stack<int> s
就是建立了一个int类型的栈，名称为s。可以通过调用它的函数来做一下关于栈的操作。
例如：
- s.empty() 如果栈为空返回true，否则返回false
- s.size() 返回栈中元素的个数
- s.pop() 删除栈顶元素但不返回其值
- s.top() 返回栈顶的元素，但不删除该元素
- s.push() 在栈顶压入新元素
计算器作业的核心计算功能就是由栈将中缀表达式转换为后缀表达式，并计算后缀表达式从而得出正确的答案。
- 中缀表达式是指一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。
- 后缀表达式是指不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，例如：(2 + 1) * 3 ， 即2 1 + 3 *。
而后缀表达式更容易被计算机解析，所以相对于中缀表达式，后缀表达式更广泛地应用于各种语言的计算之中。
- 中缀转后缀
string Data::InfixToPostfix(string infix) // 将中缀表达式转换成后缀表达式
{
char current = 0;
priority['+'] = 0;
priority['-'] = 0;
priority['*'] = 1;
priority['/'] = 1;
for (int i = 0; i < infix.size(); ++i)
{
current = infix[i];
switch (current)
{
case '0':case '1':case '2':case '3':case '4':case '5':
case '6':case '7':case '8':case '9':case '.':
postfix.push_back(current);//数字直接写入
break;
case '+':case '-':case '*':case '/':
//如果运算符的前一项不是右括号即说明前一个数字输入完毕，用#标识
if (infix[i] != ')')
postfix.push_back('#');
//如果符号栈非空，即比较目前符号与栈顶符号优先级，低于等于出栈(并写入输出字符串)，
//直至符号全部出栈或者遇到了'('或者大于栈顶符号的优先级
if (!mark.empty())
{
char tempTop = mark.top();
while (tempTop != '(' && priority[current] <= priority[tempTop])
{
postfix.push_back(tempTop);
mark.pop();
if (mark.empty())
break;
tempTop = mark.top();
}
}
mark.push(current);//新符号入栈
break;
case '(':
if (infix[i] >= '0' && infix[i] <= '9')// for expression 2-5*2(6/2)
{
postfix.push_back('#');
mark.push('*');
}
mark.push(current);
break;
case ')':
postfix.push_back('#');//右括号说明前方数字输入完成，标识一下
while (mark.top() != '(')
{
postfix.push_back(mark.top());
mark.pop();
}
mark.pop();//左括号出栈
break;
default:
break;//忽略其他字符
}
}
if (infix[infix.size() - 1] != ')')
postfix.push_back('#');//中缀表达式最后一个是数字需要加上#。
while (!mark.empty())//如果栈非空，全部出栈并写入输出字符串
{
postfix.push_back(mark.top());
mark.pop();
}
return postfix;
}
- 后缀表达式的计算
int Data::posfixCompute(string s) // 计算后缀表达式
{
string strNum;
int currNum = 0;
int tempNum = 0;
for (string::const_iterator i = s.begin(); i != s.end(); ++i)
{
switch (*i)
{
case '0':case '1':case '2':case '3':case '4':case '5':
case '6':case '7':case '8':case '9':case '.':
strNum.push_back(*i);
break;
case '+':
tempNum = tempResult.top();
tempResult.pop();
tempNum += tempResult.top();
tempResult.pop();
tempResult.push(tempNum);
break;
case '-':
tempNum = tempResult.top();
tempResult.pop();
tempNum = tempResult.top() - tempNum;
tempResult.pop();
tempResult.push(tempNum);
break;
case '*':
tempNum = tempResult.top();
tempResult.pop();
tempNum *= tempResult.top();
tempResult.pop();
tempResult.push(tempNum);
break;
case '/':
tempNum = tempResult.top();
tempResult.pop();
tempNum = tempResult.top() / tempNum;
tempResult.pop();
tempResult.push(tempNum);
break;
case '#':
currNum = atof(strNum.c_str());
strNum.clear();
tempResult.push(currNum);
break;
}
}
return tempResult.top();
}