题目
将中缀表达式翻译成后缀表达式（逆波兰表达式）时，可以去掉中缀表达式中出现的括号，简化表达式。如中缀 表达式“(2+3)6”被转成后缀表达式“23+6”后，可以借助于栈对表达式求值，完成运算。规则大致如下：
遇到操作数，则入栈；
遇到二元运算符，则连续从栈中弹出两个操作数，先弹出的做第二操作数，后弹出的做第一操作数，与该二元运 算符作用后，将得到的结果再存入栈中；
遇到一元运算符，则从栈中弹出一个操作数，与该一元运算符作用后，将得到的结果再存入栈中；
按照上面的规则，扫描后缀表达式（由键盘读到）：2、3 是操作数，依次入栈；之后碰到加号“+”这个二元运 算符，则 3、2 依次出栈，2 为第一操作数，3 为第二操作数，执行加法，和为 5，入栈；加号后面的 6 是操作数入栈；之后的乘号“*”是二元运算符，则 6、5 依次出栈，5 为第一操作数，6 为第二操作数，执行乘法，积为 30，入栈；之 后可以使用打印栈顶元素的操作（该次实验中使用命令“p”），将最后结果在屏幕上输出。
程序要求从键盘接收字符串，然后按照上面的思想，求解该字符串对应的逆波兰式表达式的值。参与计算的操作 数是实数或整数，可以是负数（将负号“n”当做是一元运算符），为了便于解析，从键盘输入的内容被分成很多行， 如上面的例子在本次实验中输入是：
2
3
+
6
*
P输出结果是：
30
程序应该提供下面的合法命令： +：弹出栈中两项元素，相加后和入栈。
-：弹出栈中两项元素，相减后差入栈。
*：弹出栈中两项元素，相乘后积入栈。
/：弹出栈中两项元素，相除后商入栈，注意如果除数为 0，系统应该通过下面的方式输出信息：
cout << "Divide by zero\n"; 同时，栈恢复到该操作之前，程序不退出。
n：表示相反数操作，弹出一项栈中元素，乘以（-1）后入栈。
d：表示复制栈顶元素操作，取出栈中一项元素，然后两次入栈。
r：表示栈顶元素与次栈顶元素交换次序，即连续出栈两项元素，再交错入栈，先出栈元素先入栈，后出栈元素后 入栈。
p：打印栈顶元素后换行，但栈中内容不变。
a：打印栈中所有元素，各元素输出时不换行，最先输出栈顶元素，最后输出栈底元素，全部输完后换一行，任务 完成后，栈中数据要维护成与操作前一致的内容。
c：清空栈中所有元素。
q：退出逆波兰式求值的程序。 注意，如果用户输入了错误的命令，则程序通过下面的方式输出信息：cout << "Bad input\n"; 栈不发生任何变化，程序不退出。 如果程序扫描碰到运算符，而栈中不存在足够的操作数弹出时，程序通过下面的方式输出信息：
cout << "Not enough operands\n";栈恢复到该操作之前，程序不退出。
Code
Dlist.h
#ifndef __DLIST_H__
#define __DLIST_H__
// Get a definition for NULL
#include <iostream>;
using namespace std;
class emptyList {
// OVERVIEW: an exception class
public:
emptyList() {}
};
template <typename T>
class Dlist {
// OVERVIEW: contains a double-ended list of Objects
public:
// Operational methods
bool isEmpty() const;
// EFFECTS: returns true if list is empty, false otherwise
void insertFront(T* o);
// MODIFIES this
// EFFECTS inserts o at the front of the list
void insertBack(T* o);
// MODIFIES this
// EFFECTS inserts o at the back of the list
T* removeFront();
// MODIFIES this
// EFFECTS removes and returns first object from non-empty list
// throws an instance of emptyList if empty
T* removeBack();
// MODIFIES this
// EFFECTS removes and returns last object from non-empty list
// throws an instance of emptyList if empty
// Maintenance methods
Dlist(); // constructor
Dlist(const Dlist& l); // copy constructor
Dlist& operator=(const Dlist& l); // assignment
~Dlist(); // destructor
private:
// A private type
struct node {
node* next;
node* prev;
T* o;
};
node* first; // The pointer to the first node (NULL if none)
node* last; // The pointer to the last node (NULL if none)
// Utility methods
void makeEmpty();
// EFFECT: called by constructors to establish empty list invariant
void removeAll();
// EFFECT: called by destructor/operator= to remove and destroy all list elements
void copyAll(const Dlist& l);
// EFFECT: called by copy constructor/operator= to copy elements
// from a source instance l to this instance
};
template<class T>
void Dlist<T>::insertFront(T* o)
{
node* temp = new node();
temp->o = o;
temp->prev = nullptr;
temp->next = first;
if (first)
first->prev = temp;
else
last = temp;
first = temp;
}
template<class T>
void Dlist<T>::insertBack(T* o) {
node* temp = new node;
temp->o = o;
temp->next = nullptr;
temp->prev = last;
if (last)
last->next = temp;
else
first = temp;
last = temp;
}
template<class T>
bool Dlist<T>::isEmpty() const {
return first == nullptr;
}
template<class T>
T* Dlist<T>::removeFront() {
if (first) {
node* temp = first;
first = first->next;
if (first)
first->prev = nullptr;
else {
first = nullptr;
last = nullptr;
}
return temp->o;
}
else {
try {
emptyList* e = new emptyList();
throw(e);
}
catch (emptyList * that) {
cout << "Not enough operands" << endl;
}
return nullptr;
}
}
template<class T>
T* Dlist<T>::removeBack() {
if (last) {
node* temp = last;
last = last->prev;
if (last)
last->next = nullptr;
else {
first = nullptr;
last = nullptr;
}
return temp->o;
}
else
{
try {
emptyList* e = new emptyList();
throw(e);
}
catch (emptyList * that) {
cout << "Not enough operands" << endl;
}
return nullptr;
}
}
template<class T>
Dlist<T>::Dlist() {
makeEmpty();
}
template<class T>
Dlist<T>::Dlist(const Dlist& l) {
copyAll(l);
}
template<class T>
Dlist<T>& Dlist<T>::operator=(const Dlist& l) // assignment
{
removeAll();
copyAll(l);
return *this;
}
template<class T>
Dlist<T>::~Dlist() {
removeAll();
}
template<class T>
void Dlist<T>::makeEmpty() {
first = nullptr;
last = nullptr;
}
template<class T>
void Dlist<T>::removeAll() {
node* p = first;
while (p) {
node* temp = p;
p = p->next;
delete temp;
}
}
template<class T>
void Dlist<T>::copyAll(const Dlist& l) {
if (l.first) {
//makeEmpty();
node* p = l.first;
node* q = new node;
first = q;
node* pq = nullptr;
while (p) {
q->o = p->o;
q->prev = pq;
pq = q;
if (!p->next)
{
last = q;
q->next = nullptr;
break;
}
q->next = new node;
q = q->next;
p = p->next;
}
}
}
#endif /* __DLIST_H__ */main.cpp
#include<iostream>
#include"Dlist.h"
using namespace std;
void BadExcepution() {
cout << "Bad input\n";
}
int main()
{
Dlist<int>integ;
Dlist<char>opera;
string str;
while (1)
{
cin >> str;
if (str == "+")
{
int* t1 = new int;
int* t2 = new int;
t1 = integ.removeFront();
t2 = integ.removeFront();
if (!t1 || !t2)
{
if (!t1 && !t2)
{
integ.insertFront(t2);
integ.insertFront(t1);
}
else if (!t1)
integ.insertFront(t2);
else if (!t2)
integ.insertFront(t1);
}
else
{
int* sum = new int;
*sum = *t1 + *t2;
integ.insertFront(sum);
}
}
else if (str == "-") {
int* t1 = new int;
int* t2 = new int;
t1=integ.removeFront();
t2 = integ.removeFront();
if (!t1 || !t2)
{
if (!t1 && !t2)
{
integ.insertFront(t2);
integ.insertFront(t1);
}
else if (!t1)
integ.insertFront(t2);
else if(!t2)
integ.insertFront(t1);
}
else
{
int* sub = new int;
*sub = *t2 - *t1;
integ.insertFront(sub);
}
}
else if (str == "/") {
int* t1 = new int;
int* t2 = new int;
t1 = integ.removeFront();
t2 = integ.removeFront();
if (!t1 || !t2)
{
if (!t1 && !t2)
{
integ.insertFront(t2);
integ.insertFront(t1);
}
else if (!t1)
integ.insertFront(t2);
else if (!t2)
integ.insertFront(t1);
}
else
{
int* ans = new int;
*ans = *t2 / *t1;
integ.insertFront(ans);
}
}
else if (str == "*") {
int* t1 = new int;
int* t2 = new int;
t1 = integ.removeFront();
t2 = integ.removeFront();
if (!t1 || !t2)
{
if (!t1 && !t2)
{
integ.insertFront(t2);
integ.insertFront(t1);
}
else if (!t1)
integ.insertFront(t2);
else if (!t2)
integ.insertFront(t1);
}
else
{
int* ans = new int;
*ans = *t1 * *t2;
integ.insertFront(ans);
}
}
else if (str == "n") {//取反
int* temp = new int;
temp = integ.removeFront();
if (temp)
{
*temp = *temp * -1;
integ.insertFront(temp);
}
}
else if (str == "d") {//重复
int* temp = new int;
temp = integ.removeFront();
if (temp)
{
integ.insertFront(temp);
integ.insertFront(temp);
}
}
else if (str == "r") {//颠倒
int* t1 = new int;
int* t2 = new int;
t1 = integ.removeFront();
t2 = integ.removeFront();
if (!t1 && !t2)
{
integ.insertFront(t2);
integ.insertFront(t1);
}
else if (!t1)
integ.insertFront(t2);
else if (!t2)
integ.insertFront(t1);
else
{
integ.insertFront(t1);
integ.insertFront(t2);
}
}
else if (str == "p") {//输出
int* temp = new int;
temp = integ.removeFront();
if (temp)
{
cout << *temp << endl;
integ.insertFront(temp);
}
}
else if (str == "a") {//全部输出
Dlist<int>* temp=new Dlist<int>();
Dlist<int>* temp2 = new Dlist<int>();
*temp = integ;
while (!temp->isEmpty()) {
temp2->insertBack(temp->removeFront());
}
while (!temp2->isEmpty()) {
cout << *(temp2->removeFront()) << " ";
}
cout << endl;
}
else if (str == "c") {//清空
while (!integ.isEmpty()) {
cout << *(integ.removeFront()) << " ";
}
}
else if (str == "q")//退出
break;
else
{
int* ans = new int(0);
bool flag = 1;
for (int i = 0; i < str.size(); i++)
{
if (str[i] > '9' || str[i] < '0')
{
BadExcepution();
flag = false;
break;
}
else
{
*ans *= 10;
*ans += str[i] - '0';
}
}
if (flag)
integ.insertFront(ans);
}
}
return 0;
}