//我只是HFUT的一个普通学生，希望把自己学习感悟更新上来
//今天已经周四，（吐舌头，张老师要求明天就交作业，确实有点晚了
//以后尽量做到周一更新一下
//原理方面我就不再赘述了，以后会说得清楚一点，下面附上我参考过的几个网页
// http://blog.csdn.net/summerxiachen/article/details/77073320
// http://blog.csdn.net/qq_34992845/article/details/70313588
//下面的代码能够实现带括号四则运算，并且处理了一位以上的整数
//感兴趣的同学，可以搜索一下前缀（波兰）、中缀和后缀（逆波兰）表达式
//另外二叉树也可以解决四则运算，稍后我会进行更新
//数据结构很难啃，大家加油
#include<iostream>
using namespace std;
//下面是我自己写的一个栈，相比于STL模板库的栈，pop()函数不仅可以删除栈顶元素，还可以将栈顶元素的值返回
template<class T>
class Stack{
public:
class Node{ //使用了链栈来实现，不懂链表的同学看一下课本，这里使用一个内部类表示每个节点
public:
T value;//用来存储当前节点的值
Node* prev = NULL;//用来存储前一个数据的地址
};
int length = 0;//栈的大小，（此处我的devc++报了一个warning，不过我懒得管了）
Node* tail = NULL;//用来记录栈顶元素的地址
Node* p = NULL;//用来作为一个中间的存储变量，没有实际意义，读者可以自行体会
void push(T val){//入栈操作
p = new Node;//用new开一个新空间，并用p记录其地址
p->value = val;//不用多说。将val的值存储
p->prev = tail;//tail指向当前的栈顶元素，而p指向待更新的栈顶元素，所以p的前一个元素肯定是当前的栈顶元素啦
tail = p;//前面说了，p只是一个中间的存储变量，所以最后还要更新tail的值，更新tail为p
length++;//栈的大小变大
}
int size(){//得到栈的大小
return length;
}
T pop(){//返回当前栈顶元素，并删除
T value = tail->value;//记录需要返回的value的值，不然一会就delete释放了
p = tail;//用中间变量p存储tail
tail = tail->prev;//将tail的地址更新为tail的前一个的地址
delete p;//现在栈顶空间已经没有用处了，所以释放掉
length--;//栈的大小变小
return value;
}
T top(){//仅返回当前栈顶元素，但不删除
return tail->value;
}
bool empty(){//判断当前栈是否为空
return length == 0;
}
};
//函数prototype写在前面，函数实现在主函数之后，前面进介绍功能，不明白的话，后面还有详细的解释
bool isNum(char);//判断一个字符是不是数字
bool comparison(char, char);//比较两个字符的大小（是按照优先级比较的），如果前一个字符大于等于后一个字符，为真
int translation(char);//这个函数是comparison的辅助函数，将'('表示为0 ,'+'和'-'均为1，'*'和'/'均为2
int operation(char, int, int);//这个是用来运算的，返回运算结果，第一个是运算符，后两个是运算数
int addition(int, int);//加法
int subtraction(int, int);//减法
int multiplication(int, int);//乘法
int division(int, int);//除法
int main(){
Stack<int> s_num;//数字栈
Stack<char> s_oper;//符号栈
bool isnum = false;//用来存储当前字符的上一个字符是不是数字，以此来解决一位以上整数的问题
//附上一个测试案例，答案算出来是3
string str = "(9-3*2)-7*2/1-((2-3+1*4)-5)*(2*12+2)/4+1";
for(int i = 0; i < str.length(); i++) {//遍历字符串的每个字符
if(isNum(str[i])) {//如果是数字
if(isnum){//如果当前数字字符的上一个字符是数字，就出栈乘10移位再加上当前的数字字符的数值，然后再入栈
s_num.push(s_num.pop() * 10 + (str[i] - '0'));
}else{//上一个不是数字，就直接入栈了
s_num.push(str[i] - '0');
isnum = true;//别忘了修改isnum的值
}
}else { //如果是符号
if(str[i] == ')'){//重点！！字符只分为两种，不可以入栈的（即')'），和可以入栈的（其他符号）
while(s_oper.top() != '(') {//一直向前扫描，直到寻找到'('
//下面这个式子有点装逼，要注意到，两个pop()函数，是先算右边的，后算左边的额，这和编译原理有关系
//如果不明白，我将等价的式子写在下面
//int num1 = s_num.pop();
//int num2 = s_num.pop();
//int result = operation(s_oper.pop(), num2, num1);
//s_num.push(result);
s_num.push(operation(s_oper.pop(), s_num.pop(), s_num.pop()));
}
s_oper.pop();//别忘了删除'('
}else{//可以入栈的，又分为可以直接入栈的，和需要进行一些操作再入栈的
//但无论如何，可不可以直接入栈，最后都要入栈，所以在if之后有一个入栈语句
//可以直接的入栈的，有三种情况
//1. 当前栈空 2.当前符号为'(' 3.当前符号的优先级大于栈顶符号(这也是为什么'('优先级定为0，避免出现意外出栈的情况)
if(!s_oper.empty() && str[i] != '(' && !comparison(str[i], s_oper.top())){//过滤掉以上三种情况
while(!s_oper.empty() && !comparison(str[i], s_oper.top())){
//栈不能空，不然怎么比较；当当前符号优先级大于栈顶的符号时，就要停止
s_num.push(operation(s_oper.pop(), s_num.pop(), s_num.pop()));//原理同上
}
}
s_oper.push(str[i]);
}
isnum = false;//别忘了修改isnum的值
}
}
while(!s_oper.empty()) {//如果遍历完了，符号栈还有元素，那么就需要出栈全部运算了才可以
s_num.push(operation(s_oper.pop(), s_num.pop(), s_num.pop()));
}
cout << s_num.pop();//输出结果
return 0;
}
bool isNum(char char_0) {//判断一个字符是不是数字
if(char_0 >= '0' && char_0 <= '9') {
return true;
}
return false;
}
bool comparison(char char_1, char char_2) {//比较函数
if(translation(char_1) > translation(char_2)) {
return true;
}
return false;
}
int translation(char char_0) {//翻译函数，将符号用数字表示
switch(char_0) {
case '(':
return 0;
case '+':
return 1;
case '-':
return 1;
case '*':
return 2;
case '/':
return 2;
default:
return 0;
}
}
int operation(char oper, int num_1, int num_2){//运算函数，分为四个子函数
switch(oper){
case '+':
return addition(num_1, num_2);
case '-':
return subtraction(num_1, num_2);
case '*':
return multiplication(num_1, num_2);
case '/':
return division(num_1, num_2);
default:
return 0;
}
}
int addition(int num_1, int num_2){
return num_1 + num_2;
}
int subtraction(int num_1, int num_2){
return num_1 - num_2;
}
int multiplication(int num_1, int num_2){
return num_1 * num_2;
}
int division(int num_1, int num_2){
return num_1 / num_2;
}
