nyoj257郁闷的c小加（一）（栈和队列）

本文主要是介绍nyoj257郁闷的c小加（一）（栈和队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

我们熟悉的表达式如a+b、a+b*(c+d)等都属于中缀表达式。中缀表达式就是（对于双目运算符来说）操作符在两个操作数中间：num1 operand num2。同理，后缀表达式就是操作符在两个操作数之后：num1 num2 operand。ACM队的“C小加”正在郁闷怎样把一个中缀表达式转换为后缀表达式，现在请你设计一个程序，帮助C小加把中缀表达式转换成后缀表达式。为简化问题，操作数均为个位数，操作符只有+-*/ 和小括号。

输入

第一行输入T，表示有T组测试数据（T<10）。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个表达式。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。并且输入数据不会出现不匹配现象。

输出

每组输出都单独成行，输出转换的后缀表达式。

样例输入

21+2(1+2)*3+4*5

样例输出

12+12+3*45*+

/**
思路：
使用一个栈，用来存放运算符；使用一个队列 ，后缀表达式；
将输入的字符串从左到右扫描一遍，如果遇到数字，则直接进入队列；
如果遇到“(”,直接进入栈，如果遇到“)”,将栈中的运算符出栈，进入队列；
如果遇到'+','-','*','/',将当前遇到的运算符str[i]与栈头的运算符opt1.top()进行优先级比较，如果str[i]的优先级小于opt1.top()的优先级，则将opt1.top()入队，将str[i]进栈， 
*/#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
int t;
char str[1010];
//stack<char>opt1;//存放运算符的栈 
//queue<char>opt2;//存放后缀表达式的队列 
int compare(char op)//设置操作符的优先级 
{if(op=='+'||op=='-'){return 1;}else if(op=='*'||op=='/'){return 2;}return 0;
}
int main()
{stack<char>opt1;queue<char>opt2;scanf("%d",&t);getchar();while(t--){while(!opt1.empty())opt1.pop();while(!opt2.empty())opt2.pop();scanf("%s",str);int len=strlen(str);opt1.push('#');for(int i=0;i<len;i++){if(str[i]>='0'&&str[i]<='9'){opt2.push(str[i]);//如果是数字，直接入队 }if(str[i]=='(')//遇到"("直接进栈 {opt1.push(str[i]);}if(str[i]==')'){while(opt1.top()!='('){//char s1=opt1.top();//	opt2.push(s1);opt2.push(opt1.top());opt1.pop();}opt1.pop();//最后把“(”出栈，但不输出 }else if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'){char s=opt1.top();while(compare(str[i])<=compare(opt1.top()))//<=就可以，小于不可以，为什么？？不解！！ {opt2.push(s);opt1.pop();s=opt1.top();}opt1.push(str[i]);}}while(!opt1.empty()){opt2.push(opt1.top());opt1.pop();}while(opt2.front()!='#')// 不以'#'结尾居然不对，不解？？？ {printf("%c",opt2.front());opt2.pop();}printf("\n");}return 0;
}

#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
using namespace std;
int t;
char str[1010];
char compare(char s,char z)//操作符优先级比较函数 
{if(s=='+'||s=='-'){if(z=='*'||z=='/'||z=='(')return '<';else return '>';}if(s=='*'||s=='/'){if(z=='(')return '<';else return '>';}if(s==')') return '<';if(s=='('||s=='#'){if((s=='('&&z==')')||(s=='#'&&z=='#'))return '=';else return '<';}
}
int main()
{stack<char>opt;int flag=0;char ch;scanf("%d",&t);getchar();while(t--){scanf("%s",str);int len=strlen(str);while(!opt.empty()){opt.pop();}opt.push('#');str[len]='#';for(int i=0;i<=len;){if(str[i]=='#'&&opt.top()=='#'){break;}if(str[i]>='0'&&str[i]<='9'||str[i]=='.'){printf("%c",str[i]);i++;flag=1;continue;} switch(compare(opt.top(),str[i])){case '<':opt.push(str[i]);i++;break;case '=':opt.pop();i++;break;case '>':ch=opt.top();opt.pop();printf("%c",ch);compare(opt.top(),str[i]);break;}}printf("\n");} return 0;
}

这篇关于nyoj257郁闷的c小加（一）（栈和队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---