Advertisement
Shiam7777777

Untitled

Apr 17th, 2019
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define ld double
  6. #define llu long long unsigned
  7.  
  8. int precedence(char op){
  9.     if(op == '+'||op == '-')
  10.     return 1;
  11.     if(op == '*'||op == '/')
  12.     return 2;
  13.     return 0;
  14. }
  15.  
  16. // Function to perform arithmetic operations.
  17. int applyOp(int a, int b, char op){
  18.     switch(op){
  19.         case '+': return a + b;
  20.         case '-': return a - b;
  21.         case '*': return a * b;
  22.         case '/': return a / b;
  23.     }
  24. }
  25.  
  26. // Function that returns value of
  27. // expression after evaluation.
  28. int evaluate(string tokens){
  29.     int i;
  30.  
  31.     // stack to store integer values.
  32.     stack <int> values;
  33.  
  34.     // stack to store operators.
  35.     stack <char> ops;
  36.  
  37.     for(i = 0; i < tokens.length(); i++){
  38.  
  39.         // Current token is a whitespace,
  40.         // skip it.
  41.         if(tokens[i] == ' ')
  42.             continue;
  43.  
  44.         // Current token is an opening
  45.         // brace, push it to 'ops'
  46.         else if(tokens[i] == '('){
  47.             ops.push(tokens[i]);
  48.         }
  49.  
  50.         // Current token is a number, push
  51.         // it to stack for numbers.
  52.         else if(isdigit(tokens[i])){
  53.             int val = 0;
  54.  
  55.             // There may be more than one
  56.             // digits in number.
  57.             while(i < tokens.length() &&
  58.                         isdigit(tokens[i]))
  59.             {
  60.                 val = (val*10) + (tokens[i]-'0');
  61.                 i++;
  62.             }
  63.  
  64.             values.push(val);
  65.         }
  66.  
  67.         // Closing brace encountered, solve
  68.         // entire brace.
  69.         else if(tokens[i] == ')')
  70.         {
  71.             while(!ops.empty() && ops.top() != '(')
  72.             {
  73.                 int val2 = values.top();
  74.                 values.pop();
  75.  
  76.                 int val1 = values.top();
  77.                 values.pop();
  78.  
  79.                 char op = ops.top();
  80.                 ops.pop();
  81.  
  82.                 values.push(applyOp(val1, val2, op));
  83.             }
  84.  
  85.             // pop opening brace.
  86.             ops.pop();
  87.         }
  88.  
  89.         // Current token is an operator.
  90.         else
  91.         {
  92.             // While top of 'ops' has same or greater
  93.             // precedence to current token, which
  94.             // is an operator. Apply operator on top
  95.             // of 'ops' to top two elements in values stack.
  96.             while(!ops.empty() && precedence(ops.top())
  97.                                 >= precedence(tokens[i])){
  98.                 int val2 = values.top();
  99.                 values.pop();
  100.  
  101.                 int val1 = values.top();
  102.                 values.pop();
  103.  
  104.                 char op = ops.top();
  105.                 ops.pop();
  106.  
  107.                 values.push(applyOp(val1, val2, op));
  108.             }
  109.  
  110.             // Push current token to 'ops'.
  111.             ops.push(tokens[i]);
  112.         }
  113.     }
  114.  
  115.     // Entire expression has been parsed at this
  116.     // point, apply remaining ops to remaining
  117.     // values.
  118.     while(!ops.empty()){
  119.         int val2 = values.top();
  120.         values.pop();
  121.  
  122.         int val1 = values.top();
  123.         values.pop();
  124.  
  125.         char op = ops.top();
  126.         ops.pop();
  127.  
  128.         values.push(applyOp(val1, val2, op));
  129.     }
  130.  
  131.     // Top of 'values' contains result, return it.
  132.     return values.top();
  133. }
  134.  
  135. int main()
  136. {
  137.     fast;
  138.     int l;
  139.     cin>>l;
  140.     string s;
  141.     getline( cin , s );
  142.     s = " " + s;
  143.     s += " ";
  144. //    cout<<s<<endl;
  145.     cout<<evaluate( s )<<endl;
  146.     return 0;
  147. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement