接頭辞式&接尾辞式&接尾辞式
何も言わずに直接テーマに行きます.
算術式の変換
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
明ちゃんはデータ構造を勉強した後、以前解決していなかった算術式が接尾辞式に変換された問題をふと思い出して、今日は解決したいと思っています.
データ構造の基礎ができた明ちゃんはすぐにこの問題を解いたが、算術式の接頭辞式と接尾辞式をどうやって求めるのかとふと思った.明ちゃんは困惑している.頭がいいから彼を助けてあげなさい.
Input
終了フラグとして'#'文字の演算式を入力します.(データはスペースがなく、入力のセットが1つしかないことを保証します)
Output
この式変換で得られた接頭辞式接頭辞式を出力します.3行に分けて出力し,順序は接頭辞式接尾辞式である.
Sample Input
Sample Output
簡から繁に入る.
1、接尾辞式:接尾辞式とは演算子がオペランドの中間にある式であるため、文字列を括弧を除いてそのまま出力するだけでよい.
2、接頭辞式(右から左へ遍歴):接頭辞式とはオペレータが前にいる式である.オペランドの相対的な順序は変わらない.
オペレータ出力の優先順位は、オペレータの優先順位に基づいて決定されます.
アルゴリズム:オペレータスタックopと演算スタックoutputsを導入します.完全な文字列を右から左に巡回します.
1、数字の場合はoutputsスタックに直接押し込む
2、現在の文字が演算子(+-*/)の場合は、次の基準に従って処理します(加算除算演算子のみを含みます).
2-1:opスタックが空またはopのスタックトップ要素が')'の場合、現在のオペレータをopスタックに直接押し込みます.
2-2:そうでない場合、現在の要素とスタックトップ要素の優先度を比較し、opスタックをスタックまたはスタックアウトします.
2-2-1:現在の要素の優先度がスタックトップ要素の優先度以上の場合、この演算子はopスタックに直接入力されます.
2-2-2:スタックトップ要素をスタックから出てoutputsスタックに押し込み、現在の演算子の優先度がスタックトップ要素の優先度またはスタックトップに等しくなるまで
要素が')'またはスタックが空です.
3、現在の演算子が')'の場合、opスタックに直接入ります.
4、現在の演算子が'('の場合、')'opスタック内のすべての演算子が表示されるまでポップアップされ、outpusスタックに順次押し込まれる
最后にまた単独で弾くことを忘れないでください.
文字列全体のループが完了するまで、上記の手順を繰り返します.
5、opスタックが空でない場合、スタック内のすべての要素をoutputsスタックに順次ポップアップします.
6、outputsスタックの要素をすべて出力します.接頭辞式です.
3、接尾辞式(左から右へ):接頭辞式とはオペレータの後の式である.オペランドの相対的な順序は変わらない.
オペレータ出力の優先順位は、オペレータの優先順位に基づいて決定されます.
アルゴリズム:オペレータスタックopと演算ベクトル空間outputsを導入します.完全な文字列を左から右に巡回します.
1、数字であればoutputsベクトルに直接押し込む
2、現在の文字が演算子(+-*/)の場合は、次の基準に従って処理します(加算除算演算子のみを含みます).
2-1:opスタックが空またはopのスタックトップ要素が'(')の場合、現在のオペレータをopスタックに直接押し込みます.
2-2:そうでない場合、現在の要素とスタックトップ要素の優先度を比較し、opスタックをスタックまたはスタックアウトします.
2-2-1:現在の要素の優先度がスタックトップ要素の優先度より大きい(厳密に大きい)場合は、この演算子をopスタックに直接入力します.
2-2-2:スタックトップ要素をスタックから出してoutputsベクトルに押し込み、現在の演算子の優先度がスタックトップ要素の優先度より大きい(厳密に大きい)まで
レベルまたはスタックトップ要素が')'またはスタックが空です.
3、現在の演算子が'('の場合はopスタックに直接入ります.
4、現在の演算子が')'の場合、'('opスタック内のすべての演算子がoutpusベクトルに順次押し込まれるまでポップアップする
最后にまた単独で弾くことを忘れないでください.
文字列全体のループが完了するまで、上記の手順を繰り返します.
5、opスタックが空でない場合、スタック内のすべての要素をoutputsベクトルに順次ポップアップします.
6、outputsベクトルの要素をすべて出力するのが接尾辞式です.
乾物コード(少し乱れているかもしれません):
算術式の変換
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
明ちゃんはデータ構造を勉強した後、以前解決していなかった算術式が接尾辞式に変換された問題をふと思い出して、今日は解決したいと思っています.
データ構造の基礎ができた明ちゃんはすぐにこの問題を解いたが、算術式の接頭辞式と接尾辞式をどうやって求めるのかとふと思った.明ちゃんは困惑している.頭がいいから彼を助けてあげなさい.
Input
終了フラグとして'#'文字の演算式を入力します.(データはスペースがなく、入力のセットが1つしかないことを保証します)
Output
この式変換で得られた接頭辞式接頭辞式を出力します.3行に分けて出力し,順序は接頭辞式接尾辞式である.
Sample Input
a*b+(c-d/e)*f#
Sample Output
+*ab*-c/def
a*b+c-d/e*f
ab*cde/-f*+
簡から繁に入る.
1、接尾辞式:接尾辞式とは演算子がオペランドの中間にある式であるため、文字列を括弧を除いてそのまま出力するだけでよい.
2、接頭辞式(右から左へ遍歴):接頭辞式とはオペレータが前にいる式である.オペランドの相対的な順序は変わらない.
オペレータ出力の優先順位は、オペレータの優先順位に基づいて決定されます.
アルゴリズム:オペレータスタックopと演算スタックoutputsを導入します.完全な文字列を右から左に巡回します.
1、数字の場合はoutputsスタックに直接押し込む
2、現在の文字が演算子(+-*/)の場合は、次の基準に従って処理します(加算除算演算子のみを含みます).
2-1:opスタックが空またはopのスタックトップ要素が')'の場合、現在のオペレータをopスタックに直接押し込みます.
2-2:そうでない場合、現在の要素とスタックトップ要素の優先度を比較し、opスタックをスタックまたはスタックアウトします.
2-2-1:現在の要素の優先度がスタックトップ要素の優先度以上の場合、この演算子はopスタックに直接入力されます.
2-2-2:スタックトップ要素をスタックから出てoutputsスタックに押し込み、現在の演算子の優先度がスタックトップ要素の優先度またはスタックトップに等しくなるまで
要素が')'またはスタックが空です.
3、現在の演算子が')'の場合、opスタックに直接入ります.
4、現在の演算子が'('の場合、')'opスタック内のすべての演算子が表示されるまでポップアップされ、outpusスタックに順次押し込まれる
最后にまた単独で弾くことを忘れないでください.
文字列全体のループが完了するまで、上記の手順を繰り返します.
5、opスタックが空でない場合、スタック内のすべての要素をoutputsスタックに順次ポップアップします.
6、outputsスタックの要素をすべて出力します.接頭辞式です.
3、接尾辞式(左から右へ):接頭辞式とはオペレータの後の式である.オペランドの相対的な順序は変わらない.
オペレータ出力の優先順位は、オペレータの優先順位に基づいて決定されます.
アルゴリズム:オペレータスタックopと演算ベクトル空間outputsを導入します.完全な文字列を左から右に巡回します.
1、数字であればoutputsベクトルに直接押し込む
2、現在の文字が演算子(+-*/)の場合は、次の基準に従って処理します(加算除算演算子のみを含みます).
2-1:opスタックが空またはopのスタックトップ要素が'(')の場合、現在のオペレータをopスタックに直接押し込みます.
2-2:そうでない場合、現在の要素とスタックトップ要素の優先度を比較し、opスタックをスタックまたはスタックアウトします.
2-2-1:現在の要素の優先度がスタックトップ要素の優先度より大きい(厳密に大きい)場合は、この演算子をopスタックに直接入力します.
2-2-2:スタックトップ要素をスタックから出してoutputsベクトルに押し込み、現在の演算子の優先度がスタックトップ要素の優先度より大きい(厳密に大きい)まで
レベルまたはスタックトップ要素が')'またはスタックが空です.
3、現在の演算子が'('の場合はopスタックに直接入ります.
4、現在の演算子が')'の場合、'('opスタック内のすべての演算子がoutpusベクトルに順次押し込まれるまでポップアップする
最后にまた単独で弾くことを忘れないでください.
文字列全体のループが完了するまで、上記の手順を繰り返します.
5、opスタックが空でない場合、スタック内のすべての要素をoutputsベクトルに順次ポップアップします.
6、outputsベクトルの要素をすべて出力するのが接尾辞式です.
乾物コード(少し乱れているかもしれません):
#include
#include
#include
#include
#include
#define N 1001
using namespace std;
bool Checking(char topchar,char localchar){
if(topchar==')'||topchar=='('){
return true;
}
else{
if(localchar=='+'||localchar=='-'){
if(topchar=='+'||topchar=='-'){
return false;//
}
else{
return false;
//
}
}
else{
if(topchar=='+'||topchar=='-'){
return true;
}
else
return false;
//
}
}
}
bool Checking2(char topchar,char localchar){
if(topchar==')'||topchar=='('){
return true;
}
else{
if(localchar=='+'||localchar=='-'){
if(topchar=='+'||topchar=='-'){
return true;//
}
else{
return false;
//
}
}
else{
return true;
//
}
}
}
int main(){
int len=0;
char str[N];//
stack op;//
stack outputs;
vector outputs2;
char c;
cin>>c;
while(c!='#'){//
str[len++]=c;
cin>>c;
}
for(int i=len-1;i>=0;i--) {// , ,
if(str[i]>='a'&&str[i]<='z'){
outputs.push(str[i]);//
}
else if(str[i]!=')'&&str[i]!='('){
if(op.empty()||op.top()==')'){
op.push(str[i]);
}
else{
if(Checking2(op.top(),str[i])){//
op.push(str[i]);
}
else{
while(true){//
outputs.push(op.top());
op.pop();
if(op.empty()||op.top()==')'||Checking2(op.top(),str[i])){
op.push(str[i]);
break;
}
}
}
}
}
else if(str[i]==')'){
op.push(str[i]);
}
else{
while(op.top()!=')'){
outputs.push(op.top());
op.pop();
}
op.pop();
}
}
while(!op.empty()){// 。
outputs.push(op.top());
op.pop();
}
while(!outputs.empty()){//
cout<='a'&&str[i]<='z'){
outputs2.push_back(str[i]);//
}
else if(str[i]!=')'&&str[i]!='('){
if(op.empty()||op.top()=='('){
op.push(str[i]);//
}
else{//
if(Checking(op.top(),str[i])){//
op.push(str[i]);
}
else{
while(true){//
outputs2.push_back(op.top());
op.pop();
if(op.empty()||op.top()=='('||Checking(op.top(),str[i])){
break;
}
}
op.push(str[i]);
}
}
}
else if(str[i]=='('){
op.push(str[i]);
}
else{
while(op.top()!='('){
outputs2.push_back(op.top());
op.pop();
}
op.pop();
}
}
while(!op.empty()){// 。
outputs2.push_back(op.top());
op.pop();
}
for(int j=0;j