USTC机试-将带括号的算术四则表达式转换为逆波兰表达式

此处用了c的stack头文件，定义stack栈，极大省去了定义栈的相关操作。

思想如下：

/**
核心思想:优先级：双栈，符号栈而言优先级大直接压，否则先弹出来,最后再将栈1中剩余符号压入数字栈2中，数字栈中数据再反向压入符号栈输出就是逆波兰表达式
中缀表达式转换为逆波兰表达式算法如下:设立两个栈，并依次从中缀表达式上取下一个字符x
1:如果x是运算数，直接将其压入栈2
2:如果x是运算符，则分以下情况讨论:
(1):如果是'('则直接压入栈1
(2):如果是')'则把栈1中位于栈顶最近的'('上的运算符弹出压入栈2中
(3):如果非括号，将其与栈1的栈顶优先级进行比较
优先级小，则把栈1中的符号弹出压入栈2直到为空或者遇到‘(’，此时把符号x压入栈1中，此处实际情况是+-已经是最低优先级，一直弹出到栈底或者遇见'('停止弹出再压入
优先级大，则直接压入栈1中，此处实际情况是*/遇见‘+-(’都直接压入，否则弹出至栈底再压入
3: 进行完步骤2后检查栈1是否是空，非空则把元素弹出再压入栈2中
4: 栈2中的元素反向压入栈1中实现逆置，栈1中弹出输出即可。
*/

代码如下：

#include<stdio.h>
#include<stack>
using namespace std;
stack<char> s;//保存运算符
stack<char> g;//保存运算数
void NIBOLAN(char *p){
    s.push('#');//#号的运算符级别最低压入栈中
	g.push('#');
	for(;*p!='\0';p++){//唯一值得学习的就是此处指针的技巧而已
		switch(*p){
		case'(':
			s.push('(');
			break;
		case')':
			while(s.top()!='('){
			   g.push(s.top());
			   s.pop();//最近左括号以上弹出压入栈g中
			}
			s.pop();//将(也弹出来，此处容易忽略
			break;
		case'+'://此处加号和减号已经是最低等级直接弹出栈中符号至‘（’,没有的话弹至栈底再压入符号
		case'-':
            while(s.top()!='#'&&s.top()!='('){
			//弹至栈底或者（
				g.push(s.top());
				s.pop();//弹出压入栈g中
			}
			s.push(*p);
		    break;
		case'*':
		case'/':
			while(s.top()!='#'){
				if(s.top()=='('||s.top()=='+'||s.top()=='-'){//左括号或者+-,直接外层压入
					break;}
			         else{
					//否则就是弹出
						g.push(s.top());
						s.pop();
					}
			}
			s.push(*p);//外层压入，此处也容易在内层if循环压入，那样的话else中的元素弹出后假如没有if中的三种情况就无法压入了所以i                                  //f阶段只跳出循环
			break;
		default://否则就是数字直接压入栈g中
			g.push(*p);
			break;
		}
	}//for循环至此结束下面再判断一下s是否剩余符号
		while(s.top()!='#'){
		//符号栈还没有压完接着弹出到数字栈
			g.push(s.top());
			s.pop();
		}//注此时栈g中是逆序，将其中数据反弹如栈s中，输出即是逆波兰表达式
		while(g.top()!='#'){
		     s.push(g.top());
		     g.pop();
		}
		while(s.top()!='#'){
			printf("%c",s.top());
		    s.pop();
		}
		printf("\n");
}
int main(){
   char s[100];
   while(scanf("%s",&s)!=EOF){
   NIBOLAN(s);
   }
return 0;
}