Postfiks ifadəsinin qiymətləndirilməsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Kahin
QalaqBaxılıb 64

Postfiks ifadə probleminin qiymətləndirilməsində a sim bir postfiks ifadəsi olan s. Verilən ifadəni qiymətləndirin.

Postfiks ifadəsinin qiymətləndirilməsiPin

misal

Giriş: s = “231 * + 9-”

Çıxış: -4

Giriş: s = “100 200 + 2/5 * 7 +”

Çıxış: 757

Tək Rəqəmli Əməliyyatlar üçün

Alqoritm

  1. Postfiks ifadəsini ehtiva edən bir simli s başlanğıc edin.
  2. Bir yaradın qalaq simli ilə eyni ölçüdədir.
  3. Yığın qayıtmazsa -1. Başqa bir ipdən keçin və cari xarakterin bir rəqəm olub olmadığını yoxlayın, rəqəmi yığının içərisinə itələyin.
  4. Başqa biri yığının içindəki ilk iki elementi açar. Mövcud xarakteri / operatoru onlara tətbiq edin və nəticələrini yığına itələyin.
  5. Yığının üst hissəsini qaytarın.

Postfiks İfadəsinin Qiymətləndirilməsi üçün C ++ Proqramı

#include <iostream>  
#include <string.h>  
  
using namespace std; 
  
struct Stack{  
    int top;  
    unsigned capacity;  
    int* array;  
};  
  
struct Stack* createStack( unsigned capacity ){  
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));  
  
    if(!stack){ 
        return NULL;  
    }    
  
    stack->top = -1;  
    stack->capacity = capacity;  
    stack->array = (int*) malloc(stack->capacity * sizeof(int));  
  
    if(!stack->array){ 
        return NULL;
    }    
  
    return stack;  
}  
  
int isEmpty(struct Stack* stack){  
    return stack->top == -1 ;  
}  
  
char peek(struct Stack* stack){  
    return stack->array[stack->top];  
}  
  
char pop(struct Stack* stack){  
    if(!isEmpty(stack)){  
        return stack->array[stack->top--];
    }    
    return '$';  
}  
  
void push(struct Stack* stack, char op){  
    stack->array[++stack->top] = op;  
}  
  
  
int evaluatePostfix(char* exp){  
    
    struct Stack* stack = createStack(strlen(exp));  
    int i;  
  
    if(!stack){ 
        return -1;
    }    
  
    for(i = 0; exp[i]; ++i){  
        if(isdigit(exp[i])){  
            push(stack, exp[i] - '0');  
        } 
        else{  
            int val1 = pop(stack);  
            int val2 = pop(stack);  
            switch (exp[i]){  
                case '+': push(stack, val2 + val1); break;  
                case '-': push(stack, val2 - val1); break;  
                case '*': push(stack, val2 * val1); break;  
                case '/': push(stack, val2/val1); break;  
            }  
        }  
    }  
    return pop(stack);  
}  
  
int main(){
    
    char s[] = "231*+9-";  
    cout<<evaluatePostfix(s); 
    
    return 0;  
}
-4

Postfiks İfadəsinin Qiymətləndirilməsi üçün Java Proqramı

import java.util.Stack; 
  
class Postfix{ 
    
    static int evaluatePostfix(String exp){ 
        
        Stack<Integer> stack=new Stack<>(); 
          
        for(int i=0;i<exp.length();i++){ 
            char c=exp.charAt(i); 
              
            if(Character.isDigit(c)){ 
                stack.push(c - '0'); 
            }    
              
            else{ 
                int val1 = stack.pop(); 
                int val2 = stack.pop(); 
                  
                switch(c){ 
                    case '+': 
                        stack.push(val2+val1); 
                        break; 
                      
                    case '-': 
                        stack.push(val2- val1); 
                        break; 
                      
                    case '/': 
                        stack.push(val2/val1); 
                        break; 
                      
                    case '*': 
                        stack.push(val2*val1); 
                        break; 
                } 
            } 
        } 
        return stack.pop();     
    } 
      
    public static void main(String[] args){
        
        String s = "231*+9-"; 
        System.out.println(evaluatePostfix(s));
        
    } 
}
-4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n), burada n verilən sətrin / ifadənin ölçüsüdür.

Köməkçi məkan: O (n), çünki n işarəsi üçün yığın boşluğundan istifadə etdik.

Birdən çox rəqəmə sahib olan əmrlər üçün

Alqoritm

  1. Postfiks ifadəsini ehtiva edən bir simli s başlanğıc edin.
  2. Simli ilə eyni ölçüdə bir yığın yaradın.
  3. Yığın qayıtmazsa -1. Başqa bir simli keçin və cari xarakterin boşluq olub olmadığını yoxlayın.
  4. Mövcud simvol bir rəqəmdirsə, bir rəqəmin olub olmadığını yoxlayın, tam ədədi oxusun, rəqəmi oxusun və rəqəmi yığında itələyin.
  5. Başqa biri yığının içindəki ilk iki elementi açar. Mövcud xarakteri / operatoru onlara tətbiq edin və nəticələrini yığına itələyin.
  6. Yığının üst hissəsini qaytarın.

Postfiks İfadəsinin Qiymətləndirilməsi üçün C ++ Proqramı

#include <iostream>  
#include <string.h>  
  
using namespace std; 
  
class Stack{  
    public: 
        int top;  
        unsigned capacity;  
        int* array;  
};  
  
Stack* createStack( unsigned capacity ){  
    Stack* stack = new Stack(); 
  
    if(!stack){
        return NULL;
    }    
  
    stack->top = -1;  
    stack->capacity = capacity;  
    stack->array = new int[(stack->capacity * sizeof(int))];  
  
    if(!stack->array){ 
        return NULL;
    }    
  
    return stack;  
}  
  
int isEmpty(Stack* stack){  
    return stack->top == -1 ;  
}  
  
int peek(Stack* stack){  
    return stack->array[stack->top];  
}  
  
int pop(Stack* stack){  
    if(!isEmpty(stack)){  
        return stack->array[stack->top--];
    }    
    return '$';  
}  
  
void push(Stack* stack,int op){  
    stack->array[++stack->top] = op;  
}  
  
  
int evaluatePostfix(char* exp){  
    
    Stack* stack = createStack(strlen(exp));  
    int i;  
  
    if(!stack){ 
        return -1;
    }    
  
    for(i = 0; exp[i]; ++i){  
        if(exp[i] == ' '){
            continue;
        }    
          
        else if(isdigit(exp[i])){  
            int num=0;  
              
            while(isdigit(exp[i])){  
                num = num * 10 + (int)(exp[i] - '0');  
                i++;  
            }  
            
            i--;  
              
            push(stack,num);  
        }  
          
        else{  
            int val1 = pop(stack);  
            int val2 = pop(stack);  
              
            switch (exp[i]){  
                case '+':
                    push(stack, val2 + val1); 
                    break;  
                case '-': 
                    push(stack, val2 - val1); 
                    break;  
                case '*': 
                    push(stack, val2 * val1); 
                    break;  
                case '/': 
                    push(stack, val2/val1);
                    break;  
            }  
        }  
    }  
    return pop(stack);   
}  
  
int main(){
    
    char s[] = "100 200 + 2 / 5 * 7 +";  
    cout<<evaluatePostfix(s); 
    
    return 0;  
}
757

Postfiks İfadəsinin Qiymətləndirilməsi üçün Java Proqramı

import java.util.Stack; 
  
class Postfix{ 
    
    static int evaluatePostfix(String exp){ 
        
        Stack<Integer> stack = new Stack<>(); 
          
        for(int i = 0; i < exp.length(); i++){ 
            char c = exp.charAt(i); 
              
            if(c == ' '){ 
                continue;
            }
              
            else if(Character.isDigit(c)){ 
                int n = 0; 
                  
                while(Character.isDigit(c)){ 
                    n = n*10 + (int)(c-'0'); 
                    i++; 
                    c = exp.charAt(i); 
                } 
                
                i--; 
  
                stack.push(n); 
            } 
              
            else{ 
                int val1 = stack.pop(); 
                int val2 = stack.pop(); 
                  
                switch(c){ 
                    case '+': 
                        stack.push(val2+val1); 
                        break; 
                      
                    case '-': 
                        stack.push(val2- val1); 
                        break; 
                      
                    case '/': 
                        stack.push(val2/val1); 
                        break; 
                      
                    case '*': 
                        stack.push(val2*val1); 
                        break; 
                } 
            } 
        } 
        return stack.pop();  
    } 
      
    public static void main(String[] args){ 
        
        String s = "100 200 + 2 / 5 * 7 +"; 
        System.out.println(evaluatePostfix(s));
        
    } 
}
757

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n), burada n verilən sətrin / ifadənin ölçüsüdür.

Köməkçi məkan: O (n), çünki n işarəsi üçün yığın boşluğundan istifadə etdik.

İstinad1   arayış2

Translate »