【C言語】接尾辞式変換(接尾辞→接尾辞)

20352 ワード

タイトルは1つの接尾辞式を入力することを説明して、プログラムはその接尾辞式を出力して、出力する接尾辞式の演算順序と入力する接尾辞式の演算順序が一致することを要求します.単純化のため、入力された接尾辞式は+(プラス)、-(マイナス)、×(乗算)、/(除算)の4つの演算記号と左右のカッコと英字からなり、算術演算子は先に乗算して減算する演算規則を遵守します.入力された接尾辞式の長さが200文字を超えず、文法エラーがなく、括弧が発生した場合、その内部には少なくとも1つの演算記号があると仮定します.
入力は1行のみで、接尾辞式
出力は1行のみで、変換後の接尾辞式です.
サンプル入力
X+A*(Y-B)-Z/F

サンプル出力
XAYB-*+ZF/-

解題の構想:2つのスタックを創立して、データの総スタックと演算子スタック、1つはすべてのデータを格納して、1つは中間過程の需要として演算子を格納します.
  • が数字に遭遇した場合、直接スタックに入る->データ総スタック
  • が演算子に遭遇した場合、1、この演算子が式の最初の演算子であるか、または'(',直接スタックに入る->演算子スタック.2,もし')':スタックのすべての演算子をスタックに追加し、'(',最後に'('スタックを出ます.3、この演算子の優先度が演算子スタックの最上位演算子より大きい場合、直接スタック->演算子スタックに入ります.そうでない場合、演算子スタックの最上位演算子はスタックを出て、その後スタック->データの合計スタックに入ります.この演算子はスタックの最上位の位置を引き継ぎ、前の演算子と比較して、演算子の優先度が前の演算子より大きいまで上記の操作を繰り返します.
  • データがすべて操作された後、スタックのすべての演算子スタックの演算子を出て、スタック->データの合計スタックに順次入力します.
  • コードは次のとおりです.
    #include 
    
    /*   */
    struct Symbol
    {
         
    	int top;
    	char s[400];
    }symbol;
    
    /*    */
    struct Number
    {
         
    	int top;
    	char n[400];
    }number;
    
    //     
    void init()
    {
         
    	symbol.top = -1;
    	number.top = -1;
    }
    
    //               
    /*   :【'*'='/'】 > 【'+'='-'】 > 【'('】 */ 
    int replace(char a)
    {
         
    	switch (a)
    	{
         
    		case '+':return 1;
    		case '-':return 1;
    		case '*':return 2;
    		case '/':return 2;
    		case '(':return 0;
    	}
    }
    
    //      
    /* s          ,e      
    	 s
    int compare(char s, char e)
    {
         
    	return (replace(s) < replace(e)) ? 1 : 0;
    }
    
    //       
    void reversePolish(char ex[])
    {
         
    	for (int i = 0; ex[i] != '\0'; i++)
    	{
         
    		/*    A-Z,         */
    		if (ex[i] <= 'Z' && ex[i] >= 'A' || ex[i] <= 'z' && ex[i] >= 'a')
    		{
         
    			number.n[++number.top] = ex[i];
    		}
    
    		else
    		{
         
    			if (symbol.top == -1) {
          symbol.s[++symbol.top] = ex[i]; continue; }
    			if (ex[i] == '(') {
          symbol.s[++symbol.top] = ex[i]; continue; }
    			/* ex[i] ')',                     ,         ')'*/
    			if (ex[i] == ')')
    			{
         
    				while (symbol.s[symbol.top] != '(')
    				{
         
    					number.n[++number.top] = symbol.s[symbol.top];
    					symbol.top--;
    				}
    				symbol.top--;
    				continue;
    			}
    			
    			/*          symbol.s[symbol.top],      ex[i]    */
    			if (compare(symbol.s[symbol.top], ex[i])) symbol.s[++symbol.top] = ex[i];
    			/*   ,   ex[i]        */
    			/*   ,            ,       ,
    			   ex[i]     ,          ,      ,
    			                       */
    			else
    			{
         
    				number.n[++number.top] = symbol.s[symbol.top];
    				symbol.s[symbol.top] = ex[i];
    				while (!compare(symbol.s[symbol.top - 1], symbol.s[symbol.top]) && symbol.top > 0)
    				{
         
    					number.n[++number.top] = symbol.s[symbol.top - 1];
    					symbol.s[symbol.top - 1] = symbol.s[symbol.top];
    					symbol.top--;
    				}
    			}
    		}
    	}
    	/*                       */
    	while (symbol.top != -1)
    	{
         
    		number.n[++number.top] = symbol.s[symbol.top];
    		symbol.top--;
    	}
    }
    
    //    (     )
    void printList()
    {
         
    	for (int i = 0; i <= number.top; i++)
    	{
         
    		printf("%c", number.n[i]);
    	}
    }
    
    int main() {
         
    	char ex[400];
    	init();
    	scanf("%s", ex);
    	reversePolish(ex);
    	printList();
    
    	return 0;
    }