栈

栈的特点

栈(Stack)是一种线性存储结构，栈中的数据元素遵守”先进后出"(First In Last Out)的原则，简称FILO结构。限定只能在栈顶进行插入和删除操作。

栈的常用方法

初始化

使用stack<int> s;来创建一个储存int类型的 stack 对象。

判断是否为空栈

使用empty()函数来判断栈是否为空。

入栈

使用push()函数来完成入栈操作。

出栈

使用pop()函数来完成入栈操作。

返回栈顶元素

使用top()函数返回栈顶元素

返回栈中元素数量

使用size()函数返回栈中元素的数目。

栈的应用

后缀表达式的转化

我们常见的算数表达式，例如1+(5-2)*3%6/3就是一个中缀表达式，而计算机不能直接进行中缀表达式的运算，需要通过栈转化为后缀表达式。
具体转换方式:

1. 创建符号栈。
2. 从左到右进行遍历。
3. 运算数,直接输出。
4. 左括号,压入符号栈。(括号是最高优先级,无需比较，入栈后优先级降到最低,确保其他符号正常入栈)
5. 右括号,(意味着括号已结束)不断弹出栈顶运算符并输出直到遇到左括号(弹出但不输出)
6. 运算符,将该运算符与栈顶运算符进行比较,如果优先级高于栈顶运算符则压入符号栈(该部分运算还不能进行),如果优先级低于等于栈顶运算符则将栈顶运算符弹出并输出,然后比较新的栈顶运算符(低于弹出意味着前面部分可以运算,先输出的一定是高优先级运算符,等于弹出是因为同等优先级,从左到右运算)直到优先级大于栈顶运算符或者栈空,再将该运算符入栈。
7. 如果对象处理完毕,则按顺序弹出并输出栈中所有运算符。

注：如果在转化的同时进行计算，需要再创建一个数字栈，在第三步中将运算数压入数字栈。每当符号栈中有元素弹出时，从数字栈弹出两个运算数进行运算，将结果压入数字栈。遍历完成后，数字栈顶元素为最终结果。

简单计算器

实现一个简单计算器¹，输入一个包含圆括号、加、减、乘、除、求余等符号组成的算术表达式字符串，输出该算术表达式的值。要求：
（1）系统至少能实现加、减、乘、除、求余等运算；
（2）利用栈的后进先出特性实现；
（3）先将输入的算术表达式转换为后缀表达式，并输出后缀表达式；
（4）利用后缀表达式输出表达式的计算结果。

关键代码：

处理算术表达式

void manage(string input){
	stack<int> number;
	stack<char> sign;
	int count=0;
	double result=0;
	string houzhui;
	while(count<input.length()){
		//判断字符还是数字
		bool yes=isSign(input[count]);
		if(yes){
			manageChar(input[count],number,sign,houzhui);
		}else{
			number.push(input[count]-'0');
			houzhui+=input[count]; 
		}
		count++;
	}
	while(!sign.empty()){
		houzhui+=sign.top();
		calculate(number,sign.top());
		sign.pop();
	}
	cout<<"后缀表达式为："; 
	cout<<houzhui<<endl;
	cout<<"计算结果为：";
	cout<<number.top()<<endl; 
}

处理字符

void manageChar(char input,stack<int> &number,stack<char> &sign,string &houzhui){ 
	if(sign.empty()||input=='('){
		sign.push(input);
	}else if(input==')'){
		while(sign.top()!='('&&!sign.empty()){
			houzhui+=sign.top();
			calculate(number,sign.top());
			sign.pop();	 
		}
		sign.pop();//弹出'('
	}else{
		 if(charWeight(input)>charWeight(sign.top())){
			sign.push(input);
		}else{
			
			do{
				houzhui+=sign.top();
				calculate(number,sign.top());
				sign.pop();
			}while(charWeight(input)<=charWeight(sign.top()));
			sign.push(input);
		}
	} 
}

运算

void calculate(stack<int> &number,char input){
	int firstNum,secondNum;
	firstNum=number.top();
	number.pop();
	secondNum=number.top();
	number.pop();
	switch(input){
	case '+':firstNum+=secondNum;break;
	case '-':firstNum=secondNum-firstNum;break;
	case '*':firstNum*=secondNum;break;
	case '/':firstNum=secondNum/firstNum;break;
	case '%':firstNum=secondNum%firstNum;break;
	default:cout<<"出错了！！！";		
	}
	number.push(firstNum);
}

运行截图