logo

TechCodeview

중위 표현식을 후위 표현식으로 변환

Infix 표현식을 Postfix 형식으로 변환하는 프로그램을 작성하세요.

중위 표현: 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에 추가됩니다.

반복적인 스캔은 매우 비효율적입니다. 중위식은 사람이 쉽게 읽고 풀 수 있는 반면, 컴퓨터는 연산자와 괄호를 쉽게 구분할 수 없으므로 평가하기 전에 식을 후위(또는 접두사) 형식으로 변환하는 것이 좋습니다.

접미사 형식의 해당 표현은 다음과 같습니다. 알파벳*+d+ . 후위 표현식은 스택을 사용하여 쉽게 평가할 수 있습니다.



Infix 표현식을 Postfix 표현식으로 변환하는 방법은 무엇입니까?

중위 표현식을 후위 표현식으로 변환하려면 다음을 사용하세요. 위의 아이디어를 구현하는 단계는 다음과 같습니다.

  1. 중위 표현 스캔 왼쪽에서 오른쪽으로 .

  2. 위의 아이디어를 구현하는 단계는 다음과 같습니다.

    1. 스캔한 문자가 피연산자인 경우 후위 표현식에 넣습니다.
    2. 위의 아이디어를 구현하는 단계는 다음과 같습니다.

      1. 그렇지 않으면 다음을 수행하십시오.
        • 스캔된 연산자의 우선순위 및 결합성이 스택에 있는 연산자의 우선순위 및 결합성보다 큰 경우[또는 스택이 비어 있거나 스택에 ' ( ' ]를 선택한 다음 스택에 푸시합니다. [' ^ ' 연산자는 오른쪽 결합이고 다른 연산자는 ' + ',' – ',' * ' 그리고 ' / '는 왼쪽 연관]입니다.
          • 특히 스택 맨 위에 있는 연산자와 스캔된 연산자가 모두 '인 경우 조건을 확인하세요. ^ '. 이 조건에서는 올바른 연관성으로 인해 스캔된 연산자의 우선순위가 더 높습니다. 따라서 연산자 스택으로 푸시됩니다.
          • 연산자 스택의 맨 위가 검색된 연산자와 동일한 다른 모든 경우에는 검색된 연산자의 우선 순위가 낮기 때문에 왼쪽 연관성으로 인해 스택에서 연산자를 팝합니다.
        • 그렇지 않으면 스캔된 연산자보다 우선순위가 크거나 같은 모든 연산자를 스택에서 팝합니다.
          • 그런 다음 스캔된 연산자를 스택에 푸시합니다. (팝업하는 동안 괄호가 나타나면 거기서 멈추고 스캔된 연산자를 스택에 푸시합니다.)
      2. 위의 아이디어를 구현하는 단계는 다음과 같습니다.

        1. 스캔한 문자가 ' ( ', 스택에 푸시합니다.
        2. 위의 아이디어를 구현하는 단계는 다음과 같습니다.

          1. 스캔한 문자가 ' ) ’, 스택을 팝하고 ‘가 나올 때까지 출력합니다. ( '가 발생하면 두 괄호를 모두 삭제합니다.
          2. 위의 아이디어를 구현하는 단계는 다음과 같습니다.

            1. 단계를 반복하세요 2-5 중위 표현식이 스캔될 때까지.
            2. 위의 아이디어를 구현하는 단계는 다음과 같습니다.

              xor cpp
              1. 스캔이 끝나면 스택을 팝하고 비어 있지 않을 때까지 접미사 표현식에 연산자를 추가합니다.
              2. 위의 아이디어를 구현하는 단계는 다음과 같습니다.

                1. 마지막으로 후위 표현식을 인쇄합니다.

                  2. 위의 아이디어를 구현하는 단계는 다음과 같습니다.

                  1. 삽화:

                  위의 아이디어를 구현하는 단계는 다음과 같습니다.

                  1. 더 나은 이해를 위해 아래 그림을 따르십시오.

                    위의 아이디어를 구현하는 단계는 다음과 같습니다.

                    1. 중위 표현을 고려하십시오 특급 = a+b*c+d
                      중위 표현식은 반복자를 사용하여 스캔됩니다. 나 , 이는 다음과 같이 초기화됩니다. 나는 = 0 .

                      1단계: 여기서 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+ .

                      팝

                      '+'를 표시하고 접미사에 추가하세요.

                      위의 알고리즘을 구현하면 다음과 같습니다.

                      씨 
                      #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 && 스택[stackIndex] != '(') { 결과[resultIndex++] = 스택[stackIndex--];  } stackIndex--; // 팝 '(' } // 연산자가 스캔되는 경우 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) { 결과[resultIndex++] = 스택[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)>
                      씨# 
                      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());  } 스택.팝(); // 팝 '(' } // 연산자가 스캔되는 경우 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) { 결과.추가(스택.팝());  } Console.WriteLine(string.Join('', 결과));  } // 드라이버 코드 static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // 함수 호출 InfixToPostfix(exp);  } }>
                      자바스크립트 
                       /* 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은 중위 표현식의 크기입니다.