Дерево выражений для двухзначных входов

Question

Я пытаюсь создать дерево выражений, которое способно вставлять двузначные числа. Прямо сейчас, он может вставлять цифры 0 - 9 из-за возможностей char. Мой текущий код работает для постфиксных выражений, поэтому, когда я создаю дерево выражений для «+52», он оценивается до 10. Если я хочу сделать выражение для 10 * 2, это не сработает, потому что мой код видит его как 3 цифры и оператора.

Вот мой код:

/* 
* C++ Program to Implement Expression Tree 
*/ 
#include <iostream> 
#include <cstdlib> 
#include <cstdio>  
#include <cstring> 
using namespace std; 

/** class TreeNode **/ 
class TreeNode 
{  
    public: 
     char data; 
     TreeNode *left, *right; 
     /** constructor **/ 
     TreeNode(char data) 
     { 
      this->data = data; 
      this->left = NULL; 
      this->right = NULL; 
     } 
}; 

/** class StackNode **/ 
class StackNode 
{  
    public: 
     TreeNode *treeNode; 
     StackNode *next; 
     /** constructor **/ 
     StackNode(TreeNode *treeNode) 
     { 
      this->treeNode = treeNode; 
      next = NULL; 
     } 
}; 


class ExpressionTree 
{ 
    private: 
     StackNode *top; 
    public: 
     /** constructor **/ 
     ExpressionTree() 
     { 
      top = NULL; 
     } 

     /** function to clear tree **/ 
     void clear() 
     { 
      top = NULL; 
     } 

     /** function to push a node **/ 

     void push(TreeNode *ptr) 
     { 
      if (top == NULL) 
       top = new StackNode(ptr); 
      else 
      { 
       StackNode *nptr = new StackNode(ptr); 
       nptr->next = top; 
       top = nptr; 
      } 
     } 

     /** function to pop a node **/ 
     TreeNode *pop() 
     { 
      if (top == NULL) 
      { 
       cout<<"Underflow"<<endl; 
      } 
      else 
      { 
       TreeNode *ptr = top->treeNode; 
       top = top->next; 
       return ptr; 
      } 
     } 

     /** function to get top node **/ 
     TreeNode *peek() 
     { 
      return top->treeNode; 
     } 


     /** function to insert character **/ 
     void insert(char val) 
     { 
      if (isDigit(val)) 
      { 
       TreeNode *nptr = new TreeNode(val); 
       push(nptr); 
      } 
      else if (isOperator(val)) 
      { 
       TreeNode *nptr = new TreeNode(val); 
       nptr->left = pop(); 
       nptr->right = pop(); 
       push(nptr); 
      } 
      else 
      { 
       cout<<"Invalid Expression"<<endl; 
       return; 
      } 
     } 

     /** function to check if digit **/ 
     bool isDigit(char ch) 
     { 
      return ch >= '0' && ch <= '9'; 
     } 

     /** function to check if operator **/ 
     bool isOperator(char ch) 
     { 
      return ch == '+' || ch == '-' || ch == '*' || ch == '/'; 
     } 


     /** function to convert character to digit **/ 
     int toDigit(char ch) 
     { 
      return ch - '0'; 
     } 

     /** function to build tree from input */ 

     void buildTree(string eqn) 
     { 
      for (int i = eqn.length() - 1; i >= 0; i--) 
       insert(eqn[i]); 
     } 

     /** function to evaluate tree */ 
     double evaluate() 
     { 
      return evaluate(peek()); 
     } 

     /** function to evaluate tree */ 
     double evaluate(TreeNode *ptr) 
     { 
      if (ptr->left == NULL && ptr->right == NULL) 
       return toDigit(ptr->data); 
      else 
      { 
       double result = 0.0; 
       double left = evaluate(ptr->left); 
       double right = evaluate(ptr->right); 
       char op = ptr->data; 
       switch (op) 
       { 
       case '+': 
        result = left + right; 
        break; 
       case '-': 
        result = left - right; 
        break; 
       case '*': 
        result = left * right; 
        break; 
       case '/': 
        result = left/right; 
        break; 
       default: 
        result = left + right; 
        break; 
       } 
       return result; 
      } 
     } 


}; 



/** Main Contains menu **/ 
int main() 
{ 
    string s; 
    cout<<"Expression Tree Test"<<endl; 
    ExpressionTree et; 
    et.buildTree("*52"); 
    cout<<"\n\nEvaluated Result : "<<et.evaluate(); 
} 

Как сделать так, чтобы код способен обрабатывать и оценивать две цифры номера?

Answer 1

Прежде всего, '+ 5 2' называется префиксом, а не postfix обозначение. Я не уверен, хотите ли вы преобразовать свой код для обработки выражений infix (5 + 2), для чего вам потребуется переписать всю вещь в значительной степени или префиксные выражения с несколькими цифрами (+ 10 5), в любом случае вы, вероятно, хотите учитывать пробелы во входной строке.

Вы должны изменить Treenode.data как int вместо char, так как реалистично вы ожидаете, что «+ 10 5» будет проанализировано как три treeNodes в целом, один из которых будет содержать «10».

Обычный способ сделать это - сначала разбить входную строку на tokens перед тем, как передать коллекцию маркеров в buildTree. Входная строка «+ 10 5» должна сначала стать вектором/массивом, содержащим строки «+», «10», «5». Затем, когда вы передадите эту коллекцию buildTree, каждый элемент станет новым TreeNode.

Кроме этого, глядя на ваш код, класс StackNode кажется излишним; вы должны иметь возможность делать все, что хотите, имея только TreeNode.