本文主要是介绍nyoj-257-郁闷的C小加（一 ）中缀式变后缀式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：here~~~~~~~
今天看了此题，感觉栈和队列很好用，进一步深入了解
一个算术表达式，含有数字（为简化处理，数字只有一位），运算符：+、-、*，以及括号，求表达式的值。
给出的表达式是一般我们见到的中缀表达式，即运算符位于操作数之间。如果把中缀表达式转化为后缀表达式，那么对后缀表达式求值将会很方便。
后缀表达式特点：
1.操作符位于操作数之后；
2.没有括号；
3.运算符没有优先级。
中缀表达式转化为后缀表达式的步骤：
1.初始化一个空操作符栈和空结果字符串；
2.从前到后读取中缀表达式的字符，如果是操作数，加到结果字符串后面；
3.如果是操作符，分两种情况入栈：
a.如果待入栈操作符优先级大于栈顶操作符，直接入栈；
b.如果待入栈操作符优先级小于或等于栈顶操作符，栈顶操作符加到结果字符串后面；重复b过程直到遇到前括号‘(’或栈顶操作符优先级比待入栈操作符小，待入栈操作符入栈。
4.如果是前括号‘(’，直接入栈；
5.如果是后括号，将栈中操作符依次弹出，直至遇到一个前括号‘(’结束。前括号出栈。
最后结果字符串就是后缀表达式。
后缀表达式求值的步骤：
1.初始化一个空操作数栈；
2.从前到后读取后缀表达式字符。如果是操作数直接入栈。如果读到一个操作符@，弹出栈顶元素a和新的栈顶元素b，执行b @ a，将结果压入栈中；
3.最后栈中只剩下一个元素，即表达式的值。
原链接 ：http://www.cnblogs.com/xiaofanke/archive/2013/05/29/3106391.html经典的数据结构题，用栈跟队列模拟。
中缀式变后缀式：
stack optr;用来存放运算符栈。队列queue opnd用来存放后缀表达式。
从左到右扫描中缀表达式，是操作数就放进队列 opnd的末尾。
如果是运算符的话，分为下面3种情况：
(1）如果是‘（’直接压入optr栈。
(2）如果是‘）’，依次从optr栈弹出运算符加到队列 opnd的末尾，直到遇到'（'；
(3) 如果是非括号，比较扫描到的运算符，和optr栈顶的运算符。如果扫描到的运算符优先级高于栈顶运算符
则，把运算符压入栈。否则的话，就依次把栈中运算符弹出加到队列 opnd的末尾，直到遇到优先级低于扫描
到的运算符或栈空，并且把扫描到的运算符压入栈中。
就这样依次扫描，知道结束为止。
如果扫描结束，栈中还有元素，则依次弹出加到队列 opnd的末尾，就得到了后缀表达式。
原链接：点击打开链接
#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
using namespace std;
queue<char> Q;
stack<char> S;
int priority(char s)
{if(s=='+'||s=='-') return 1;if(s=='*'||s=='/') return 2;if(s=='(') return 0;return -1;
}
int main()
{int n,i,l;char str[1100];S.push('#');scanf("%d",&n);while(n--){getchar();scanf("%s",str);l=strlen(str);for(i=0;i<l;i++){if(str[i]>='0'&&str[i]<='9') Q.push(str[i]);else if(str[i]=='(') S.push(str[i]);else if(str[i]==')'){while(S.top()!='('){Q.push(S.top());S.pop();}S.pop();}else{while(priority(S.top())>=priority(str[i])){Q.push(S.top());S.pop();}S.push(str[i]);}}while(S.top()!='#'){Q.push(S.top());S.pop();}while(!Q.empty()){printf("%c",Q.front());Q.pop();}printf("\n");}
}
这篇关于nyoj-257-郁闷的C小加（一 ）中缀式变后缀式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
