Как я могу преобразовать инфикс в постфиксное выражение многозначных операндов?

Question

Я могу преобразовать инфикс в постфикс и вычислять с одной цифрой, но я не могу преобразовать в постфикс и вычислить с помощью N цифр. PLz, кто-нибудь мне поможет! Благодаря!!

вот мой код с одной цифрой

#include<iostream> 
#include<stdio.h> 
#include<string.h> 
#include<math.h> 
#include<stdlib.h> 

using namespace std; 

class infix2postfix 
{ 
public: 
    void push(int symbol); 
    int pop(); 
    void infix_to_postfix(); 
    int priority(char symbol); 
    int isEmpty(); 
    int white_space(char); 
    int eval_post(); 
}; 

char infix[100], postfix[100]; 
int stack[100]; 
int top; 

int main() 
{ 
    infix2postfix ip; 
    top=-1; 
    cout<<"Enter infix : "; 
    gets(infix); 
    ip.infix_to_postfix(); 
    cout<<"Postfix : "<<postfix<<endl; 
    cout<<"Result is : "<<ip.eval_post()<<endl; 
    return 1; 
} 

void infix2postfix :: infix_to_postfix() 
{ 
    int i,p=0; 
    char next; 
    char symbol; 
    for(i=0; i<strlen(infix); i++) 
    { 
     symbol=infix[i]; 
     if(!white_space(symbol)) 
     { 
      switch(symbol) 
      { 
      case '(': 
       push(symbol); 
       break; 
      case ')': 
       while((next=pop())!='(') 
        postfix[p++] = next; 
       break; 
      case '+': 
      case '-': 
      case '*': 
      case '/': 
      case '%': 
      case '^': 
       while(!isEmpty() && priority(stack[top])>= priority(symbol)) 
        postfix[p++]=pop(); 
       push(symbol); 
       break; 
      default: /*if an operand comes*/ 
       postfix[p++]=symbol; 
      } 
     } 
    } 
    while(!isEmpty()) 
     postfix[p++]=pop(); 
    postfix[p]='\0'; /*End postfix with'\0' to make it a string*/ 
} 

/*This function returns the priority of the operator*/ 
int infix2postfix :: priority(char symbol) 
{ 
    switch(symbol) 
    { 
    case '(': 
     return 0; 
    case '+': 
    case '-': 
     return 1; 
    case '*': 
    case '/': 
    case '%': 
     return 2; 
    case '^': 
     return 3; 
    default : 
     return 0; 
    } 
} 

void infix2postfix :: push(int symbol) 
{ 
    if(top>100) 
    { 
     cout<<"Stack overflow\n"; 
     exit(1); 
    } 
    stack[++top]=symbol; 
} 

int infix2postfix :: pop() 
{ 
    if(isEmpty()) 
    { 
     cout<<"Stack underflow\n"; 
     exit(1); 
    } 
    return (stack[top--]); 
} 

int infix2postfix :: isEmpty() 
{ 
    if(top==-1) 
     return 1; 
    else 
     return 0; 
} 

int infix2postfix :: white_space(char symbol) 
{ 
    if(symbol == ' ' || symbol == '\t') 
     return 1; 
    else 
     return 0; 
} 

int infix2postfix :: eval_post() 
{ 
    int a,b,i,temp,result; 
    for(i=0; i<strlen(postfix); i++) 
    { 
     if(postfix[i]<='9' && postfix[i]>='0') 
      push(postfix[i]-'0'); 
     else 
     { 
      a=pop(); 
      b=pop(); 
      switch(postfix[i]) 
      { 
      case '+': 
       temp=b+a; 
       break; 
      case '-': 
       temp=b-a; 
       break; 
      case '*': 
       temp=b*a; 
       break; 
      case '/': 
       temp=b/a; 
       break; 
      case '%': 
       temp=b%a; 
       break; 
      case '^': 
       temp=pow(b,a); 
      } 
      push(temp); 
     } 
    } 
    result=pop(); 
    return result; 
} 

Мой вопрос: как получить результат для более чем 1 разрядным операндом? Я пробовал для одной цифры, но как я могу получить для многозначных чисел?

Answer 1

Вы в настоящее время нажимаете цифры в стеке индивидуально, поэтому числовое значение 10 будет вытолкнуто в стеке двумя символами: 1 и 0.

В вашей логике оператора вы выписываете один символ из стека за каждый операнд. Таким образом, многозначные операнды не будут работать и будут давать совершенно неправильные результаты.

Существует много способов решить эту проблему. Например, вы можете объединить несколько цифр вместе в один и тот же символ стека при их чтении (т. Е. Объединить цифру, обрабатываемую в настоящий момент с вершиной стека, если оба являются цифрами).

Место для этого было бы внутри push. Вот как это сделать:

void infix2postfix :: push(int symbol) 
{ 
    if(top>100) 
    { 
     cout<<"Stack overflow\n"; 
     exit(1); 
    } 
    if (! isEmpty() && stack[top] >= 0 && stack[top] <= 9) { 
     stack[top] *= 10; 
     stack[top] += symbol; 
    } 
    else { 
     stack[++top]=symbol; 
    } 
} 

Это будет работать до тех пор, как числовой операнд помещается внутри диапазона в междунар. Большие числа просто переполняются.

Будут также проблемы, потому что цифры не могут быть указаны отдельно от других символов стека. С многозначными числами теперь вы можете иметь символы, которые имеют то же значение int, что и оператор. Способ исправить это - назначить отрицательные значения int символам оператора и неотрицательные значения для чисел. Это будет работать для вашего дела, так как ваша грамматика, похоже, не имеет унарного минуса. Этот подход также соответствует тому, что вы делаете в eval_post, где вы нажимаете результат вычисления в стеке как единое целочисленное значение, независимо от того, сколько цифр может содержаться.

Самая мощная, но сложная альтернатива могла бы написать грамматику и использовать генератор синтаксического анализатора. Я рекомендую GNU bison. Это полностью возьмет на себя процесс генерации кода для синтаксического анализатора, поэтому все, что вам нужно сделать, это написать грамматику для ваших выражений плюс фактическое преобразование infix-to-postfix (что будет тривиально с бизоном). Это также поможет вам легко обнаружить недопустимый ввод и предоставить соответствующие сообщения об ошибках.

Однако, начинать с бизона может быть сложно, если вы никогда не использовали его раньше.