My Pastes
Public Pastes
Layout Width
Share Pastebin
Guest
Public paste!

asdf

By: a guest | Mar 16th, 2010 | Syntax: C++ | Size: 3.14 KB | Hits: 34 | Expires: Never
Download | Raw | Embed | Report abuse
Copy text to clipboard
  1. #include <iostream>
  2.  
  3. #include <string>
  4.  
  5. #include <stack>
  6.  
  7. #include "BinaryTree.cpp"
  8.  
  9. using namespace std;
  10.  
  11.  
  12.  
  13. void createTree(const string & postfix);
  14.  
  15. void toPostFix(const string & infix, string & postfix);
  16.  
  17. bool isOperand(char ch);
  18.  
  19. bool hasPrecedence(char OperatorA, char OperatorB);
  20.  
  21.  
  22.  
  23. int main(void) {
  24.  
  25.         string infix, postfix; // local to this loop
  26.  
  27.         cout << endl << endl << "Enter an infix expression: ";
  28.  
  29.         cin >> infix;
  30.  
  31.         toPostFix(infix, postfix);
  32.  
  33.         cout << endl << "The equivalent postfix expression is: " << postfix << endl << endl;
  34.  
  35.         createTree(postfix);
  36.  
  37.         cout << endl << endl << endl;
  38.  
  39.         return 0;
  40.  
  41. }
  42.  
  43.  
  44.  
  45. bool isOperand(char ch)
  46.  
  47. {
  48.  
  49.         if (((ch >= 'a') && (ch <= 'z')) || ((ch >= 'A') && (ch <= 'Z')) || ((ch >= '0') && (ch <= '9')))
  50.  
  51.                 return true;
  52.  
  53.         else return false;
  54.  
  55. }
  56.  
  57.  
  58.  
  59. bool hasPrecedence(char OperatorA, char OperatorB)
  60.  
  61. {
  62.  
  63.         if (OperatorA == '(') return false;
  64.  
  65.         else if (OperatorB == '(') return false;
  66.  
  67.         else if (OperatorB == ')') return true;
  68.  
  69.         else if ((OperatorA == '^') && (OperatorB == '^')) return false;
  70.  
  71.         else if (OperatorA == '^') return true;
  72.  
  73.         else if (OperatorB == '^') return false;
  74.  
  75.         else if ((OperatorA == '*') || (OperatorA == '/')) return true;
  76.  
  77.         else if ((OperatorB == '*') || (OperatorB == '/')) return false;
  78.  
  79.         else
  80.  
  81.                 return true;
  82.  
  83. }
  84.  
  85.  
  86.  
  87.  
  88.  
  89. void toPostFix(const string & infix, string & postfix)
  90.  
  91. {
  92.  
  93.         stack<char> OperatorStack;
  94.  
  95.         char TopSymbol, Symbol;
  96.  
  97.         int k;
  98.  
  99.  
  100.  
  101.         for (k = 0; k < infix.size(); k++)
  102.  
  103.         {
  104.  
  105.                 Symbol = infix[k];
  106.  
  107.                 if (isOperand(Symbol))
  108.  
  109.                         postfix = postfix + Symbol;
  110.  
  111.                 else {
  112.  
  113.                         while ((! OperatorStack.empty()) && (hasPrecedence(OperatorStack.top(), Symbol))) {
  114.  
  115.                                 TopSymbol = OperatorStack.top();
  116.  
  117.                                 OperatorStack.pop();
  118.  
  119.                                 postfix = postfix + TopSymbol;
  120.  
  121.                         }
  122.  
  123.                         if ((! OperatorStack.empty()) && (Symbol == ')'))
  124.  
  125.                                 OperatorStack.pop(); // discard matching (
  126.  
  127.                         else
  128.  
  129.                                 OperatorStack.push(Symbol);
  130.  
  131.                 }
  132.  
  133.         }
  134.  
  135.  
  136.  
  137.         while (! OperatorStack.empty())
  138.  
  139.         {
  140.  
  141.                 TopSymbol = OperatorStack.top();
  142.  
  143.                 OperatorStack.pop();
  144.  
  145.                 postfix = postfix + TopSymbol;
  146.  
  147.         }
  148.  
  149. }
  150.  
  151. void createTree(const string & postfix) {
  152.  
  153.         stack<Tree> s;
  154.  
  155.         for (int i=0; i<postfix.length(); i++) {
  156.  
  157.                 if (isOperand(postfix[i])) {
  158.  
  159.                         Tree *t;
  160.  
  161.                         t=new Tree(postfix[i],NULL,NULL);
  162.  
  163.                         s.push(*t);
  164.  
  165.                 }
  166.  
  167.                 else {
  168.  
  169.                         Tree *tc;
  170.  
  171.                         Tree ta=s.top();
  172.  
  173.                         s.pop();
  174.  
  175.                         Tree tb=s.top();
  176.  
  177.                         s.pop();
  178.  
  179.                         tc = new Tree(postfix[i],&tb,&ta);
  180.  
  181.                         s.push(*tc);
  182.  
  183.                 }
  184.  
  185.         }
  186.  
  187.         Tree *mytree;
  188.  
  189.         mytree = &s.top();
  190.  
  191.         s.pop();
  192.  
  193.         cout << " Tree is " << mytree->RootData() << " with left " << mytree->Left()->RootData() << " and right " << mytree->Right()->RootData() << endl;
  194.  
  195.         (mytree->Right()->Left() == NULL) ? cout << endl : cout << mytree->Right()->Left()->RootData() << endl;
  196.  
  197.         (mytree->Right()->Right() == NULL) ? cout << endl : cout << mytree->Right()->Right()->RootData() << endl;
  198.  
  199.         cout << " Tree is " << mytree->Left()->RootData() << " with left " << mytree->Left()->Left()->RootData() << " and right " << mytree->Left()->Right()->RootData() << endl;
  200.  
  201.         //mytree->preorder(mytree);
  202.  
  203.         return;
  204.  
  205. }
create new paste | create new version of this paste RAW Paste Data