후 위에서 중위로 변환


난이도 쉽게
자주 묻는 질문 아마존 팩트 셋 Microsoft
수학 스택

접미사에서 중위로 변환 문제에서 접미사 표기법으로 표현했습니다. 주어진 표기법을 중위 표기법으로 변환하는 프로그램을 작성하십시오.

중위 표기법

이 표기법에서 연산자는 피연산자 사이에 기록됩니다. 우리가 일반적으로 표현을 쓰는 것과 비슷합니다.

예를 들어 : A + B는 중위 식입니다.

후위 표기법

이 표기법에서 피연산자는 연산자 앞에 기록됩니다. 역 폴란드어 표기법이라고도합니다.

예 : AB +는 접미사 표현식입니다.

접미사 표기법으로 표현이 주어졌습니다. 주어진 표기법을 중위 표기법으로 변환하는 프로그램을 작성하십시오.

후 위에서 중위로 변환

입력 : 접미사 : ABC / -AD / E- *

출력 : 중위 : ((A- (B / C)) * ((A / D) -E))

입력 : 접미사 : AB + CD- *

출력 : 중위 : ((A + B) * (CD))

후 위에서 중위로 변환을위한 알고리즘

  1. 초기화 접미사 표현을 포함합니다.
  2. 만들기 스택 문자열 유형의 s.
  3. 문자열의 시작에서 끝까지 순회하고 현재 문자가 피연산자인지 확인하여 스택의 문자열로 푸시합니다.
  4. 그렇지 않으면 스택에서 두 개의 최상위 문자를 꺼내서 두 번째 문자 + 현재 연산자 + 첫 번째 문자로 연결합니다. 문자열을 스택으로 다시 밀어 넣으십시오.
  5. 스택의 맨 위를 반환합니다.

후 위에서 중위로 변환을위한 구현

C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
bool isOperand(char x){ 
   return((x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z')); 
} 
  
string postfixToInfix(string postfix_exp){ 
    stack<string> s; 
  
    for(int i=0; postfix_exp[i]!='\0'; i++){ 

        if(isOperand(postfix_exp[i])){ 
           string op(1, postfix_exp[i]); 
           s.push(op); 
        } 
  
        else{ 
            string op1 = s.top(); 
            s.pop(); 
            string op2 = s.top(); 
            s.pop(); 
            s.push("(" + op2 + postfix_exp[i] + op1 + ")"); 
        } 
    } 
    return s.top(); 
} 
int main(){
    string postfix_exp = "ABC/-AD/E-*"; 
    cout<<"Infix : "<<postfixToInfix(postfix_exp); 
    return 0; 
}
Infix : ((A-(B/C))*((A/D)-E))

자바 프로그램

import java.util.*; 
class Postfix{      
    static boolean isOperand(char x)
    { 
      return (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'); 
    }       
    static String postfixToInfix(String postfix_exp){ 
        Stack<String> s = new Stack<String>(); 
        for(int i = 0; i<postfix_exp.length(); i++)
        { 
            if(isOperand(postfix_exp.charAt(i))){ 
                s.push(postfix_exp.charAt(i) + ""); 
            }      
            else
            { 
                String op1 = s.peek(); 
                s.pop(); 
                String op2 = s.peek(); 
                s.pop(); 
                s.push("(" + op2 + postfix_exp.charAt(i) + op1 + ")"); 
            } 
        }       
        return s.peek(); 
    }       
    public static void main(String args[]){        
        String postfix_exp = "ABC/-AD/E-*";
        System.out.println("Infix : "+postfixToInfix(postfix_exp));       
    } 
}
Infix : ((A-(B/C))*((A/D)-E))

후 위에서 중위로 변환을위한 복잡성 분석

시간 복잡성 : O (n) 여기서 n은 접미사 문자열의 길이입니다.

공간 복잡성 : 공백을 사용하여 문자열의 n 개 문자를 각각 저장하므로 O (n).

참조