접두사에서 접미사로 변환


난이도 중급
자주 묻는 질문 아마존 팩트 셋 광신자 신탁
스택

접두사에서 접미사로의 변환 문제에서 접두사 표기법으로 표현을 체재. 주어진 표기법을 접미사 표기법으로 변환하는 프로그램을 작성하십시오.

접두사 표기법

이 표기법에서는 연산자 뒤에 피연산자를 씁니다. 폴란드 표기법이라고도합니다.

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

후위 표기법

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

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

접두사에서 접미사로 변환

입력 : 접두사 : * -A / BC- / ADE

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

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

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

접두사에서 후 위로 변환을위한 알고리즘

  1. 접두사 식을 포함하는 문자열을 초기화합니다.
  2. 문자열 유형의 스택을 만듭니다.
  3. 마지막 문자에서 문자열의 첫 번째 문자로 이동하고 현재 문자가 연산자인지 확인합니다. 스택 둘 다 뒤에 현재 연산자를 사용하여 단일 문자열로 연결하십시오. 문자열을 스택으로 다시 밀어 넣으십시오.
  4. 그렇지 않으면 현재 문자가 연산자가 아니면 스택의 문자열로 푸시합니다.
  5. 스택의 맨 위를 반환합니다.

실시

접두사에서 후 위로 변환을위한 C ++ 프로그램

#include <iostream> 
#include <stack> 
using namespace std; 

bool isOperator(char x){ 
    switch (x){ 
        case '+': 
        case '-': 
        case '/': 
        case '*': 
            return true; 
    } 
    return false; 
} 

string prefixToPostfix(string prefix_exp){ 

    stack<string> s; 
    
    int l = prefix_exp.size(); 
    
    for(int i = l-1; i >= 0; i--){ 
    
        if(isOperator(prefix_exp[i])){ 
            string op1 = s.top(); 
            s.pop(); 
            string op2 = s.top(); 
            s.pop(); 
            
            string temp = op1 + op2 + prefix_exp[i]; 
            
            s.push(temp); 
        } 
        
        else{ 
            s.push(string(1, prefix_exp[i])); 
        } 
    } 
    
    return s.top(); 
} 

int main(){ 

    string prefix_exp = "*-A/BC-/ADE"; 
    cout<<"Postfix : "<<prefixToPostfix(prefix_exp); 
    
    return 0; 
}
Postfix : ABC/-AD/E-*

접두사에서 후 위로 변환을위한 Java 프로그램

import java.util.*; 
  
class Prefix{ 
  
    static boolean isOperator(char x){ 
        switch (x){ 
            case '+': 
            case '-': 
            case '/': 
            case '*': 
                return true; 
        } 
        return false; 
    } 
      
    static String prefixToPostfix(String prefix_exp){ 
      
        Stack<String> s= new Stack<String>(); 
      
        int l = prefix_exp.length(); 
      
        for(int i = l-1; i >= 0; i--){ 
            if(isOperator(prefix_exp.charAt(i))){ 
      
                String op1 = s.peek(); 
                s.pop(); 
                String op2 = s.peek(); 
                s.pop(); 
      
                String temp = op1 + op2 + prefix_exp.charAt(i); 
      
                s.push(temp); 
            } 
      
            else{ 
                s.push(prefix_exp.charAt(i)+""); 
            } 
        } 
      
        return s.peek(); 
    } 
      
    public static void main(String args[]){
        
        String prefix_exp = "*-A/BC-/ADE"; 
        System.out.println("Postfix : " + prefixToPostfix(prefix_exp)); 
        
    } 
}
Postfix : ABC/-AD/E-*

복잡성 분석

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

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

참조