MouseyN1

2Stacks expression evaluation

Apr 17th, 2016
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.72 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <stack>
  5. #include <cctype>
  6. using namespace std;
  7.  
  8. bool error;
  9.  
  10. bool hasLowerPriority(char op1, char op2)   {
  11.     switch (op1) {
  12.         case '(': return false;
  13.         case '-': return op2 == '-';
  14.         case '+': return op2 == '-' || op2 == '+';
  15.         case '*': return op2 != '/';
  16.         case '/': return true;
  17.         default : error = true; return false;
  18.     }
  19. }
  20.  
  21. stack < char > operators;
  22. stack < int > operands;
  23.  
  24. void operation(char op) {
  25.     if(operands.size() < 2) {
  26.         error = true; return;
  27.     }
  28.     int op2 = operands.top(); operands.pop();
  29.     int op1 = operands.top(); operands.pop();
  30.     switch(op)  {
  31.         case '+': operands.push(op1 + op2); break;
  32.         case '-': operands.push(op1 - op2); break;
  33.         case '*': operands.push(op1 * op2); break;
  34.         case '/': operands.push(op1 / op2); break;
  35.         default : error = true; return;
  36.     }
  37. }
  38.  
  39. int main()  {
  40.     char exp[1000], *p;
  41.     int len;
  42.  
  43.     while(true) {
  44.         printf("\nEnter an expression (x to exit):\n");
  45.         scanf("%[^\n]%*c", exp);
  46.         if(exp[0] == 'x' || exp[0] == 'X') break;
  47.  
  48.         len = strlen(exp);
  49.         if(len == 0) {
  50.             getchar();
  51.             continue;
  52.         }
  53.         exp[len] = ' ';
  54.         exp[len + 1] = ')';
  55.         exp[len + 2] = '\0';
  56.         error = false;
  57.         operators.push('(');
  58.  
  59.         p = strtok(exp, " ");
  60.         while(p && !error) {
  61.             if(isdigit(p[0]))
  62.                 operands.push(atoi(p));
  63.             else switch(p[0]) {
  64.                 case '(':
  65.                     operators.push('(');
  66.                     break;
  67.                 case ')':
  68.                     while(!operators.empty() && !error && operators.top() != '(') {
  69.                         operation(operators.top());
  70.                         operators.pop();
  71.                     }
  72.                     if (!operators.empty())
  73.                         operators.pop();
  74.                     else
  75.                         error = true;
  76.                     break;
  77.                 default:
  78.                     while(!operators.empty() && !error && hasLowerPriority(operators.top(), p[0])) {
  79.                         operation(operators.top()); operators.pop();
  80.                     }
  81.                     operators.push(p[0]);
  82.             }
  83.             p = strtok(NULL, " ");
  84.         }
  85.         if(error || !operators.empty() || operands.size() != 1) {
  86.             printf("ERROR\n");
  87.             while(!operands.empty())
  88.                 operands.pop();
  89.             while(!operators.empty())
  90.                 operators.pop();
  91.         }
  92.         else printf("%d\n", operands.top()); operands.pop();
  93.     }
  94.     return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment