c++接尾辞式回転接尾辞式および接尾辞式の計算

みんなの批判と是正を歓迎する
接尾辞式変換接尾辞式および接尾辞式の計算
一、接尾辞式回転接尾辞式
手順:1.2つの空きスタックS 1,S 2を用意する
2.数字が直接S 1に押し込まれると
3.操作シンボルに遭遇した場合、S 2が空である場合、または現在のシンボルの優先度がS 2スタックトップオペレータの優先度より大きい場合、または'('左かっこ)、またはS 2スタックトップが'('左かっこ)である場合、現在のオペレータは直接S 2に押し込まれる
4.オペレータに遭遇した場合、現在のオペレータの優先度がS 2スタックトップオペレータの優先度以下である場合、S 2はスタックトップをポップアップし、S 2が空になるまでS 1を押し込むか、左かっこ'(')、または現在のシンボルの優先度未満である場合、現在のシンボルをS 2に押し込む
5.右括弧')'に遭遇した場合、S 2はスタックの上部をポップアップし、S 1を押して左括弧'('をポップアップするまで、括弧を省略する
6.最後に、S 2スタックをポップアップし、S 1が空になるまで押し込む.
このときS 1が格納する逆の順序が接尾辞式である
例:
1+(3-4 x 2+5)/2を接尾辞式に変換します.
まず、2つの空きスタックS 1,S 2を持ってきて、順次遍歴式から.
「1」は数字であり、S 1;'+'に直接圧入する.は符号であり、S 2は空であり、S 2を押し込む.(’左括弧はS 2に直接圧入する;‘3’は数字で、直接S 1に圧入する;‘−’は記号で、S 2スタックの頂上は‘(’,‘−’を直接S 2に圧入する;‘4’は数字であり,直接S 1に圧入する;‘x’は記号であり,S 2スタックトップは‘−’であり,優先度‘x’>‘−’であり,‘x’をS 2に圧入する;‘2’は数字であり,直接S 1に圧入する;‘+’は記号であり,S 2スタックトップは‘x’であり,優先度‘x’>‘+’であり,S 2スタックトップをポップアップし,S 1を圧入し,S 2スタックトップ優先度が‘+’より小さくなるまで,’+’圧入S 2;’2’は数字であり、S 1;')に直接圧入する.右括弧に遭遇して、S 2スタックの頂上を絶えずポップアップし始め、S 1に押し込む.左かっこに出会ったことを知って、かっこを捨てます;'/'シンボルであり、S 2スタックの上部は「-」、優先度「/」>「-」であり、「x」をS 2に押し込む.その後、S 2スタックの上部を順次ポップアップし、S 1に押し込み、S 2が空であることを知る.その後、S 1スタックの上部を順次ポップアップし、S 2を押し込み、S 1が空であることを知る.その後、S 2スタックトップを順次ポップアップし、出力する.

       ：

1 3 4 2 x - 5+2/+

   1+（3-4x2+5）/2      。

//           
#include
#include
#include
using namespace std;

int to_int(char c){
	return c - '0';
}
int to_r(char c){//     
	if (c == '+' || c == '-')return 1;
	else if (c == '*' || c == '/')return 2;
}
int main(){
	stack<char> s1, s2;
	string str; cin >> str;
	for (int i = 0; i < str.length(); i++){
		if (str[i] >= '0'&&str[i] <= '9'){
			s1.push(str[i]);
		}
		else{
			if (s2.empty()||str[i] == '('){//  s2           
				s2.push(str[i]);
			}
			else if (str[i] == ')'){   //  ，              
				while (s2.top() != '('){
					s1.push(s2.top());
					s2.pop();
				}
				s2.pop();
			}
			else if (s2.top() == '('||to_r(str[i])>to_r(s2.top())  ){
				s2.push(str[i]);
			}		
			else if (to_r(str[i]) <= to_r(s2.top())){
				while (!s2.empty() && to_r(str[i]) <= to_r(s2.top())){
					s1.push(s2.top());
					s2.pop();
					if (s2.top() == '(')break;
				}
				s2.push(str[i]);
			}
		}
	}
	while (!s2.empty()){
		s1.push(s2.top());
		s2.pop();
	}
	while (!s1.empty()){
		s2.push(s1.top());
		s1.pop();
	}
	while(!s2.empty()){
		cout << s2.top() << " ";
		s2.pop();
	}

	system("pause");
	return 0;
}

二、接尾辞式の計算
手順:1.もう一度スタックs 3を持ってきてください.2.上記のs 2スタックの上部をポップアップし、オペレータに遭遇するまでs 3を押し込む.3.s 3スタックトップの次の加算/減算/乗算/除算で、結果をs 3に圧入する.3.このようにs 2が空になるまで、s 3は接尾辞式の演算結果である要素が1つしかない.
例:
上記接尾辞式1 3 4 2 x-5+2/+1入スタック、3入スタック、4入スタック、2入スタック、x計算4 x 2得8、入スタック.このときスタック内の要素は1 3 8(8はスタックトップ);'-'3-8を計算すると-5がスタックに入り、このときスタック要素は1-5(-5がスタックトップ)5がスタックに入り、+計算-5+5が0がスタックに入り、このときスタック要素は1 0(0がスタックトップ)2がスタックに入り、/計算0/2が0がスタックに入り、このときスタック要素は1 0(0がスタックトップ)「+」計算1+0が接尾辞式の結果となる.
コード#コード#

//                        
#include
#include
#include
using namespace std;

int to_int(char c){
	return c - '0';
}
int to_r(char c){//     
	if (c == '+' || c == '-')return 1;
	else if (c == '*' || c == '/')return 2;
}
int op(int a, int b, char c){ //  
	if (c == '+')return a + b;
	else if (c == '-')return a - b;
	else if (c == '*')return a*b;
	else if (c == '/')return a / b;
}
int main(){
	stack<char> s1, s2;
	string str; cin >> str;
	for (int i = 0; i < str.length(); i++){
		if (str[i] >= '0'&&str[i] <= '9'){
			s1.push(str[i]);
		}
		else{
			if (s2.empty()||str[i] == '('){
				s2.push(str[i]);
			}
			else if (str[i] == ')'){
				while (s2.top() != '('){
					s1.push(s2.top());
					s2.pop();
				}
				s2.pop();
			}
			else if (s2.top() == '('||to_r(str[i])>to_r(s2.top())  ){
				s2.push(str[i]);
			}		
			else if (to_r(str[i]) <= to_r(s2.top())){
				while (!s2.empty() && to_r(str[i]) <= to_r(s2.top())){
					s1.push(s2.top());
					s2.pop();
					if (s2.top() == '(')break;
				}
				s2.push(str[i]);
			}
		}
	}
	while (!s2.empty()){
		s1.push(s2.top());
		s2.pop();
	}
	while (!s1.empty()){
		s2.push(s1.top());
		s1.pop();
	}
	
	stack<int> s3;
	while (!s2.empty()){
		if (s2.top() >= '0'&&s2.top() <= '9'){
			s3.push(to_int(s2.top()));
			s2.pop();
		}
		else{
			int a = s3.top(); s3.pop();
			int b = s3.top(); s3.pop();
			int c = op(b, a, s2.top());
			s2.pop();
			s3.push(c);
		}
	}
	cout << s3.top() << endl;
	system("pause");
	return 0;
}