fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <math.h>
  5.  
  6. class Token
  7. {
  8. public:
  9.     Token(const char);
  10.     Token(std::string num);
  11.     enum Type { RBracket, LBracket, Num, Space, Dot, Add, Sub, Div, Mul, Pow, Undefined };
  12.     enum Priority { Low, Average, High, Braces };
  13.     std::string symbol();
  14.     Type type();
  15.     Priority priority();
  16.  
  17. private:
  18.     std::string _symbol;
  19.     Type _type;
  20.     Priority _priority;
  21.  
  22. };
  23.  
  24. // TODO: add Undefined
  25. Token::Token(char ch)
  26. {
  27.     _symbol = ch;
  28.  
  29.     if (isdigit(ch))
  30.         _type = Num;
  31.  
  32.     switch (ch) {
  33.     case ' ':
  34.         _type = Space;
  35.         break;
  36.     case '.':
  37.         _type = Dot;
  38.         break;
  39.     case '+':
  40.         _type = Add;
  41.         _priority = Low;
  42.         break;
  43.     case '-':
  44.         _type = Sub;
  45.         _priority = Low;
  46.         break;
  47.     case '/':
  48.         _type = Div;
  49.         _priority = Average;
  50.         break;
  51.     case '*':
  52.         _type = Mul;
  53.         _priority = Average;
  54.         break;
  55.     case '^':
  56.         _type = Pow;
  57.         _priority = High;
  58.         break;
  59.     case '(':
  60.         _type = LBracket;
  61.         _priority = Braces;
  62.         break;
  63.     case ')':
  64.         _type = RBracket;
  65.         _priority = Braces;
  66.         break;
  67.     }
  68. }
  69.  
  70. // It is always number
  71. Token::Token(std::string num)
  72. {
  73.     _type = Num;
  74.     _symbol = num;
  75. }
  76.  
  77. std::string Token::symbol()
  78. {
  79.     return _symbol;
  80. }
  81.  
  82. Token::Type Token::type()
  83. {
  84.     return _type;
  85. }
  86.  
  87. Token::Priority Token::priority()
  88. {
  89.     return _priority;
  90. }
  91.  
  92. std::vector<Token> toRPN(std::string str)
  93. {
  94.     size_t len = str.length();
  95.     std::string number; // glue number
  96.     bool glueNumber = false;  // we are alrady gluing?
  97.     int prevType;
  98.     std::vector<Token> tokens;
  99.     std::vector<Token> result;
  100.  
  101.     for (unsigned i = 0; i < len; ++i) {
  102.         Token tok(str[i]);
  103.         if (tok.type() == Token::Undefined)
  104.             fprintf(stderr, "Undefined token <%s>\n", tok.symbol().c_str());
  105.         if (tok.type() == Token::Space) {
  106.             if (glueNumber) {
  107.                 result.push_back(Token(number));
  108.                 glueNumber = false;
  109.                 number.clear();
  110.             }
  111.             continue;
  112.         }
  113.  
  114.         if (tok.type() == Token::Sub) {
  115.             if (prevType != Token::Num) {
  116.                 if (!glueNumber) {
  117.                     number += tok.symbol();
  118.                 } else {
  119.                     fprintf(stderr, "Undefined token <%s>\n", tok.symbol().c_str());
  120.                 }
  121.                 continue;
  122.             }
  123.         }
  124.  
  125.         // For determine if minus (-) is '-3' or '5 - 3'
  126.         prevType = tok.type();
  127.  
  128.         // It is dot without number .4 + 3
  129.         if (tok.type() == Token::Dot) {
  130.             if (glueNumber) {
  131.                 number += tok.symbol();
  132.             } else {
  133.                 fprintf(stderr, "Undefined token <%s>\n", tok.symbol().c_str());
  134.             }
  135.             continue;
  136.         }
  137.  
  138.         if (tok.type() == Token::Num) {
  139.             number += tok.symbol();
  140.             glueNumber = true;
  141.             if (i == len - 1) {
  142.                 result.push_back(Token(number));
  143.             }
  144.         } else {
  145.             if (glueNumber) {
  146.                 result.push_back(Token(number));
  147.                 glueNumber = false;
  148.                 number = "";
  149.             }
  150.  
  151.             while(tokens.size() > 0 && tok.type() != Token::RBracket) {
  152.                 Token prev = tokens.back();
  153.                 if (prev.priority() >= tok.priority() && prev.priority() != Token::Braces) {
  154.                     result.push_back(prev);
  155.                     tokens.pop_back();
  156.                 } else {
  157.                     break;
  158.                 }
  159.             }
  160.  
  161.             if (tok.type() != Token::RBracket)
  162.                 tokens.push_back(tok);
  163.         }
  164.  
  165.         if (tok.type() == Token::RBracket) {
  166.             Token prev = tokens.back();
  167.             while (prev.type() != Token::LBracket) {
  168.                 result.push_back(prev);
  169.                 tokens.pop_back();
  170.                 prev = tokens.back();
  171.             }
  172.             tokens.pop_back(); // delete LBracket
  173.         }
  174.     }
  175.  
  176.     // Reverse iteration. Add remaining tokens to result
  177.     for (std::vector<Token>::reverse_iterator rit = tokens.rbegin(); rit!= tokens.rend(); ++rit) {
  178.         result.push_back(*rit);
  179.     }
  180.  
  181.     return result;
  182. }
  183.  
  184. // If exspression will ended with error we'll show it!
  185. std::string calculateError;
  186. double calculate(std::vector<Token> tokens)
  187. {
  188.     std::vector<double> stack;
  189.     double val1;
  190.     double val2;
  191.     double result;
  192.  
  193.     // If it was any error we have to clear it!
  194.     calculateError.clear();
  195.  
  196.     for (Token &tok : tokens) {
  197.  
  198.         if (tok.type() == Token::Num) {
  199.             stack.push_back(atof(tok.symbol().c_str()));
  200.             continue;
  201.         }
  202.  
  203.         // Minimum for operation
  204.         if (stack.size() > 1) {
  205.  
  206.             // Get last two numbers from stack
  207.             val2 = stack.back();
  208.             stack.pop_back();
  209.             val1 = stack.back();
  210.             stack.pop_back();
  211.  
  212.             switch (tok.type()) {
  213.             case Token::Add:
  214.                 stack.push_back(val1 + val2);
  215.                 break;
  216.             case Token::Sub:
  217.                 stack.push_back(val1 - val2);
  218.                 break;
  219.             case Token::Mul:
  220.                 stack.push_back(val1 * val2);
  221.                 break;
  222.             case Token::Div:
  223.                 if (val2 == 0) {
  224.                     calculateError.append("Divided by zero");
  225.                 }
  226.                 stack.push_back(val1 / val2);
  227.                 break;
  228.             case Token::Pow:
  229.                 stack.push_back(pow(val1, val2));
  230.                 break;
  231.             default:
  232.                 break;
  233.             }
  234.         } else {
  235.             calculateError.append("Does not correct expression");
  236.             break;
  237.         }
  238.     }
  239.  
  240.     if (stack.size() == 1) {
  241.         double temp = stack.back();
  242.         result = temp;
  243.     } else {
  244.         calculateError.append("Does not correct expression");
  245.     }
  246.  
  247.     return result;
  248. }
  249.  
  250. void test_calculate()
  251. {
  252.     std::list<std::string> lst;
  253.     lst.push_back("2 + 3");
  254.     lst.push_back("4 - 3");
  255.     lst.push_back("2 + (-3)");
  256.     lst.push_back("4 * 5");
  257.     lst.push_back("6/4");
  258.     lst.push_back("1.2 + 1/2");
  259.     lst.push_back("1/(-3)");
  260.     lst.push_back("0.5 + 0.2");
  261.     lst.push_back("3 ^ 2 ^ 2");
  262.     lst.push_back("17654/342");
  263.     lst.push_back("2/3 ^ 2");
  264.     lst.push_back("(2/3) ^ 2");
  265.     lst.push_back("(2 + 3) / (2 - 2) ");
  266.     lst.push_back("2 + 345 + + + + 6 ");
  267.  
  268.     std::vector<Token> tokens;
  269.     double result;
  270.     std::string resultOfRPN;
  271.     for (std::string &item : lst) {
  272.         tokens = toRPN(item);
  273.         for (Token &tok : tokens) {
  274.             resultOfRPN.append(tok.symbol() + " ");
  275.         }
  276.         result = calculate(tokens);
  277.  
  278.         if (calculateError.size() == 0)
  279.             printf("%-18s %.6g\n", resultOfRPN.c_str(), result);
  280.         else
  281.             printf("%-18s %s\n", resultOfRPN.c_str(), calculateError.c_str());
  282.  
  283.         // reset
  284.         resultOfRPN.clear();
  285.     }
  286. }
  287.  
  288. int main()
  289. {
  290.     test_calculate();
  291.  
  292.     return 0;
  293. }
  294.  
Success #stdin #stdout 0s 3444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 3 +              5
4 3 -              1
2 -3 +             -1
4 5 *              20
6 4 /              1.5
1.2 1 2 / +        1.7
1 -3 /             -0.333333
0.5 0.2 +          0.7
3 2 ^ 2 ^          81
17654 342 /        51.6199
2 3 2 ^ /          0.222222
2 3 / 2 ^          0.444444
2 3 + 2 2 - /      Divided by zero
2 345 + + + + 6 +  Does not correct expression
https://ideone.com/Gxgken
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!