logo

TechCodeview

中置式を後置式に変換する

中置式を後置式に変換するプログラムを作成します。

中置式: a 演算子 b (a + b) の形式の式。つまり、演算子がすべてのオペランドのペアの間にある場合。
後置式: a b 演算子 (ab+) 形式の式。つまり、すべてのオペランドのペアの後に演算子が続きます。



例:

入力： A + B * C + D
出力： ABC*+D+

入力： ((A + B) – C * (D / E)) + F
出力： AB+CDE/*-F+



なぜ式を後置表現にするのでしょうか?

コンパイラは式を左から右または右から左のいずれかにスキャンします。
次の式を考えてみましょう。 a + b * c + d

  • コンパイラは、最初に式をスキャンして式 b * c を評価し、次に式を再度スキャンしてそれに a を追加します。
  • 結果は、別のスキャン後に d に追加されます。

スキャンを繰り返すと非常に非効率になります。中置式は人間が読みやすく解くことができますが、コンピュータは演算子と括弧を簡単に区別できないため、評価する前に式を後置(または前置)形式に変換することをお勧めします。

後置形式の対応する式は次のとおりです。 abc*+d+ 。後置式はスタックを使用して簡単に評価できます。



中置式を後置式に変換するにはどうすればよいですか?

中置式を後置式に変換するには、 上記のアイデアを実装する手順は次のとおりです。

  1. 中置式をスキャンします 左から右へ 。

  2. 上記のアイデアを実装する手順は次のとおりです。

    1. スキャンした文字がオペランドの場合は、それを後置式に置きます。
    2. 上記のアイデアを実装する手順は次のとおりです。

      1. それ以外の場合は、次の操作を行ってください
        • スキャンされた演算子の優先順位と結合性が、スタック内の演算子の優先順位と結合性よりも大きい場合 (またはスタックが空であるか、スタックに ‘ が含まれている場合) ( ‘ ] を選択してスタックにプッシュします。 [「 ^ ‘ 演算子は右結合であり、他の演算子は ‘ + 「、」 – 「、」 * ' そして ' / ' は左結合です]。
          • 特にスタックの最上位の演算子とスキャンされた演算子が両方とも ‘ である場合の条件を確認してください。 ^ 「。」この状況では、適切な結合性により、スキャンされた演算子の優先順位が高くなります。したがって、オペレータースタックにプッシュされます。
          • 他のすべての場合、演算子スタックの最上位がスキャンされた演算子と同じである場合、スキャンされた演算子の優先順位が低い左結合性により、演算子をスタックからポップします。
        • それ以外の場合は、スキャンされた演算子以上の優先順位を持つすべての演算子をスタックからポップします。
          • それを行った後、スキャンされたオペレーターをスタックにプッシュします。 (ポップ中に括弧が見つかった場合は、そこで停止し、スキャンされた演算子をスタックにプッシュします。)
      2. 上記のアイデアを実装する手順は次のとおりです。

        1. スキャンした文字が「」の場合 ( '、スタックにプッシュします。
        2. 上記のアイデアを実装する手順は次のとおりです。

          1. スキャンした文字が「」の場合 ) '、スタックをポップし、' になるまで出力します。 ( ' が見つかった場合は、両方の括弧を破棄します。
          2. 上記のアイデアを実装する手順は次のとおりです。

            1. 手順を繰り返す 2-5 中置式がスキャンされるまで。
            2. 上記のアイデアを実装する手順は次のとおりです。

              jsの複数行の文字列
              1. スキャンが終了したら、スタックをポップし、空でなくなるまで後置式に演算子を追加します。
              2. 上記のアイデアを実装する手順は次のとおりです。

                1. 最後に、後置式を出力します。

                  2. 上記のアイデアを実装する手順は次のとおりです。

                  1. 図：

                  上記のアイデアを実装する手順は次のとおりです。

                  1. よりよく理解するには、以下の図に従ってください

                    上記のアイデアを実装する手順は次のとおりです。

                    1. 中置式を考慮してください exp = a+b*c+d
                      そして中置式は反復子を使用してスキャンされます 私 、次のように初期化されます i = 0 。

                      最初のステップ: ここで、i = 0 および exp[i] = 'a'、つまりオペランドです。したがって、これを後置式に追加します。したがって、 後置 = a 。

                      追加

                      接尾辞に「a」を追加します

                      第 2 ステップ: ここで、i = 1 および exp[i] = '+'、つまり演算子です。これをスタックにプッシュします。 後置 = a そして スタック = {+} 。

                      押す

                      スタックに「+」をプッシュします

                      3番目のステップ: ここで、i = 2 および exp[i] = 'b'、つまりオペランドです。したがって、これを後置式に追加します。 後置 = ab そして スタック = {+} 。

                      GFG

                      接尾辞に「b」を追加します

                      4番目のステップ: ここで、i = 3 および exp[i] = ‘*’、つまり演算子です。これをスタックにプッシュします。 後置 = ab そして スタック = {+, *} 。

                      押す

                      スタックに「*」をプッシュします

                      5番目のステップ: ここで、i = 4 および exp[i] = 'c'、つまりオペランドです。これを後置式に追加します。 後置 = abc そして スタック = {+, *} 。

                      追加

                      接尾辞に「c」を追加します

                      6番目のステップ: ここで、i = 5 および exp[i] = '+'、つまり演算子です。スタックの最上位の要素の優先順位が高くなります。したがって、スタックが空になるか、最上位の要素の優先順位が低くなるまでポップします。 「*」はポップされて後置に追加されます。それで 後置 = abc* そして スタック = {+} 。

                      ポップ

                      「*」をポップして接尾辞を追加します

                      現在、最上位の要素は ‘ + ' それも優先順位が低いわけではありません。ポンと弾いてみよう。 後置 = abc*+ 。

                      ポップ

                      「+」をポップして後置に追加します

                      これでスタックは空になりました。だから押してください 「+」 スタック内にあります。 スタック = {+} 。

                      押す

                      スタックに「+」をプッシュします

                      7番目のステップ: ここで、i = 6 および exp[i] = 'd'、つまりオペランドです。これを後置式に追加します。 後置 = abc*+d 。

                      追加

                      接尾辞に「d」を追加します

                      最終段階： これで要素は何もなくなりました。したがって、スタックを空にして後置式に追加します。 後置 = abc*+d+ 。

                      ポップ

                      「+」をポップして後置に追加します

                      上記のアルゴリズムの実装を以下に示します。

                      C 
                      #include  #include  #include  // Function to return precedence of operators int prec(char c)  c == '-')  return 1;  else  return -1;  // Function to return associativity of operators char associativity(char c) {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative } // The main function to convert infix expression to postfix expression void infixToPostfix(char s[]) {  char result[1000];  int resultIndex = 0;  int len = strlen(s);  char stack[1000];  int stackIndex = -1;  for (int i = 0; i < len; i++) {  char c = s[i];  // If the scanned character is an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9')) {  result[resultIndex++] = c;  }  // If the scanned character is an ‘(‘, push it to the stack.  else if (c == '(') {  stack[++stackIndex] = c;  }  // If the scanned character is an ‘)’, pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')') {  while (stackIndex>= 0 && stack[stackIndex] != '(') { result[resultIndex++] = stack[stackIndex--];  スタックインデックス--; // Pop '(' } // 演算子がスキャンされた場合 else { while (stackIndex>= 0 && (prec(s[i])< prec(stack[stackIndex]) ||  prec(s[i]) == prec(stack[stackIndex]) &&  associativity(s[i]) == 'L')) {  result[resultIndex++] = stack[stackIndex--];  }  stack[++stackIndex] = c;  }  }  // Pop all the remaining elements from the stack  while (stackIndex>= 0) { result[resultIndex++] = stack[stackIndex--];  結果[結果インデックス] = ' ';  printf('%s
', 結果); } // ドライバー コード int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // 関数呼び出し infixToPostfix(exp);  0を返します。 }>>
                      ジャワ 
                      import java.util.Stack; public class InfixToPostfix {  // Function to return precedence of operators  static int prec(char c)   // Function to return associativity of operators  static char associativity(char c) {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative  }  // The main function to convert infix expression to postfix expression  static void infixToPostfix(String s) {  StringBuilder result = new StringBuilder();  Stackスタック = 新しいスタック();  for (int i = 0; i< s.length(); i++) {  char c = s.charAt(i);  // If the scanned character is an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9')) {  result.append(c);  }  // If the scanned character is an ‘(‘, push it to the stack.  else if (c == '(') {  stack.push(c);  }  // If the scanned character is an ‘)’, pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')') {  while (!stack.isEmpty() && stack.peek() != '(') {  result.append(stack.pop());  }  stack.pop(); // Pop '('  }  // If an operator is scanned  else {  while (!stack.isEmpty() && (prec(s.charAt(i)) < prec(stack.peek()) ||  prec(s.charAt(i)) == prec(stack.peek()) &&  associativity(s.charAt(i)) == 'L')) {  result.append(stack.pop());  }  stack.push(c);  }  }  // Pop all the remaining elements from the stack  while (!stack.isEmpty()) {  result.append(stack.pop());  }  System.out.println(result);  }  // Driver code  public static void main(String[] args) {  String exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Function call  infixToPostfix(exp);  } }>
                      パイソン 
                      def prec(c): if c == '^': return 3 elif c == '/' or c == '*': return 2 elif c == '+' or c == '-': return 1 else: return -1 def associativity(c): if c == '^': return 'R' return 'L' # Default to left-associative def infix_to_postfix(s): result = [] stack = [] for i in range(len(s)): c = s[i] # If the scanned character is an operand, add it to the output string. if ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9'): result.append(c) # If the scanned character is an ‘(‘, push it to the stack. elif c == '(': stack.append(c) # If the scanned character is an ‘)’, pop and add to the output string from the stack # until an ‘(‘ is encountered. elif c == ')': while stack and stack[-1] != '(': result.append(stack.pop()) stack.pop() # Pop '(' # If an operator is scanned else: while stack and (prec(s[i]) < prec(stack[-1]) or (prec(s[i]) == prec(stack[-1]) and associativity(s[i]) == 'L')): result.append(stack.pop()) stack.append(c) # Pop all the remaining elements from the stack while stack: result.append(stack.pop()) print(''.join(result)) # Driver code exp = 'a+b*(c^d-e)^(f+g*h)-i' # Function call infix_to_postfix(exp)>
                      C# 
                      using System; using System.Collections.Generic; class Program {  // Function to return precedence of operators  static int Prec(char c)   c == '*')  return 2;  else if (c == '+'   // Function to return associativity of operators  static char Associativity(char c)  {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative  }  // The main function to convert infix expression to postfix expression  static void InfixToPostfix(string s)  {  Stackスタック = 新しいスタック();  リスト結果 = 新しいリスト();  for (int i = 0; i< s.Length; i++)  {  char c = s[i];  // If the scanned character is an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9'))  {  result.Add(c);  }  // If the scanned character is an ‘(‘, push it to the stack.  else if (c == '(')  {  stack.Push(c);  }  // If the scanned character is an ‘)’, pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')')  {  while (stack.Count>0 && stack.Peek() != '(') { result.Add(stack.Pop());  スタック.ポップ(); // Pop '(' } // 演算子がスキャンされた場合 else { while (stack.Count> 0 && (Prec(s[i])< Prec(stack.Peek()) ||  Prec(s[i]) == Prec(stack.Peek()) &&  Associativity(s[i]) == 'L'))  {  result.Add(stack.Pop());  }  stack.Push(c);  }  }  // Pop all the remaining elements from the stack  while (stack.Count>0) { result.Add(stack.Pop());  Console.WriteLine(string.Join('', result));  } // ドライバー コード static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // 関数呼び出し InfixToPostfix(exp);  } }>>
                      JavaScript 
                       /* Javascript implementation to convert  infix expression to postfix*/    //Function to return precedence of operators  function prec(c)  c == '-')  return 1;  else  return -1;    // The main function to convert infix expression  //to postfix expression  function infixToPostfix(s) {  let st = []; //For stack operations, we are using JavaScript built in stack  let result = '';  for(let i = 0; i < s.length; i++) {  let c = s[i];  // If the scanned character is  // an operand, add it to output string.  if((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9'))  result += c;  // If the scanned character is an  // ‘(‘, push it to the stack.  else if(c == '(')  st.push('(');  // If the scanned character is an ‘)’,  // pop and to output string from the stack  // until an ‘(‘ is encountered.  else if(c == ')') {  while(st[st.length - 1] != '(')  {  result += st[st.length - 1];  st.pop();  }  st.pop();  }  //If an operator is scanned  else {  while(st.length != 0 && prec(s[i]) <= prec(st[st.length - 1])) {  result += st[st.length - 1];  st.pop();   }  st.push(c);  }  }  // Pop all the remaining elements from the stack  while(st.length != 0) {  result += st[st.length - 1];  st.pop();  }  console.log(result + '');  }    let exp = 'a+b*(c^d-e)^(f+g*h)-i';  infixToPostfix(exp); // This code is contributed by decode2207.>
                      C++14 
                      #include  using namespace std; // Function to return precedence of operators int prec(char c)  c == '*')  return 2;  else if (c == '+'  // Function to return associativity of operators char associativity(char c) {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative } // The main function to convert infix expression // to postfix expression void infixToPostfix(string s) {  stackセント;  文字列の結果。  for (int i = 0; i< s.length(); i++) {  char c = s[i];  // If the scanned character is  // an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9'))  result += c;  // If the scanned character is an  // ‘(‘, push it to the stack.  else if (c == '(')  st.push('(');  // If the scanned character is an ‘)’,  // pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')') {  while (st.top() != '(') {  result += st.top();  st.pop();  }  st.pop(); // Pop '('  }  // If an operator is scanned  else {  while (!st.empty() && prec(s[i]) < prec(st.top()) ||  !st.empty() && prec(s[i]) == prec(st.top()) &&  associativity(s[i]) == 'L') {  result += st.top();  st.pop();  }  st.push(c);  }  }  // Pop all the remaining elements from the stack  while (!st.empty()) {  result += st.top();  st.pop();  }  cout << result << endl; } // Driver code int main() {  string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Function call  infixToPostfix(exp);  return 0; }>
                      出力 
                      abcd^e-fgh*+^*+i->

                      時間計算量: O(N)、N は中置式のサイズです
                      補助スペース: O(N)、N は中置式のサイズです