Stack.hpp
#pragma once
template <class T>
class Stack{
private:
T* _array;
size_t _capacity;
int _topindex;
public:
Stack()          //构造函数
:_array(0)
， _capacity(0)
， _topindex(-1)
{}
void Push(const T& x){                         //入栈操作
if (_topindex + 1 == _capacity){
_capacity = 2 * _capacity + 3;
T* tmp = new T[_capacity];
if (tmp == NULL){
cout << "failed new" << endl;
exit(-1);
}
memcpy(tmp， _array， sizeof(T) * (_topindex + 1));
delete _array;
_array = tmp;
}
_array[++_topindex] = x;
}
void Pop(){                                      //出栈
if (_topindex > -1){
//cout << _array[_topindex] << endl;
_topindex--;
}
}
bool empty(){                  //清空
return _topindex = -1;
}
const T& top(){                             //取栈顶元素
//cout << _array[_topindex] << endl;
return _array[_topindex];
}
};
main.cpp
#include<iostream>
#include<string>
#include"Stack.hpp"
using namespace std;
enum Type{
ADD，
SUB，
MUL，
DIV，
OP_NUM，
};
struct Cell{
Type _type;
int num;
};
Cell RPNExp[] = {
OP_NUM， 12，
OP_NUM， 3，
OP_NUM， 4，
ADD， 1，
MUL， 1，
OP_NUM， 6，
SUB， 1，
OP_NUM， 8，
OP_NUM， 2，
DIV， 1，
ADD， 1，
};
int main(){
Stack<int> s2;
int i = 0;
for (int i = 0; i < sizeof(RPNExp) / sizeof(RPNExp[0]);i++){  //取出元素
int left， right;             //两个操作数
switch (RPNExp[i]._type){        //将栈中数据出栈
case ADD:                         //如果是加号，取两个操作数
left = s2.top();
s2.Pop();
right = s2.top();
s2.Pop();
s2.Push(left + right);         //新的值入栈
break;
case SUB:                       //如果是减号，取两个操作数
left = s2.top();
s2.Pop();
right = s2.top();
s2.Pop();
s2.Push(right - left);
break;
case MUL:                         //如果是乘号，取两个操作数
left = s2.top();
s2.Pop();
right = s2.top();
s2.Pop();
s2.Push(left * right);
break;
case DIV:                        //如果是除号，取两个操作数
left = s2.top();
s2.Pop();
right = s2.top();
s2.Pop();
s2.Push(right / left);
break;
case OP_NUM:                     //如果数字，入栈
s2.Push(RPNExp[i].num);
break;
default:
return -1;
}
}
cout << s2.top() << endl;
return 0;
}