Question

Using stacks, write an infix expression parser. Here are a few examples of expressions your program should parse and evaluate: Result Expression 1+2 3 7 2+2 2 3 14 0//or false if the type is bool 1 // or true if the type is bool 1==2 1+3 2 (4> 4) & & 0 (1+2) 3 0 //or false if the type is bool 9 ++++2-5* (3^2) -41 Technical Requirements (Weight: 20%) Your parser should parse an infix expression that supports the following arithmetic and logical operators with the specified precedencies: Precedence Example 1 0 (false) ++2 /3 Operator !//1ogical not +//prefix increment 8 /prefix decrement //negative A//power /, //arithmetic -2 //1 8 _ -1 //-1 2 3 8 2 // 12 6 2//4 6 6 //arithmetic + 5 6 5 //1 (true) 6! 5 / 1 (true) >, >=, <, <= //comparison ==, != //equality comparison //logical and //1oqical OR 4 6>5 && 4>5 //0 (false) 1 0//1 && 2 (true) (Weight: 30%) Parse an expression given in a string format. Your program should be flexible with the given expressions. For instance, 1+2 is the same as 1 2. The user should not worry about writing the spaces between operands and operators. (Weight: 20%) Your program should check for invalid expressions, and produce meaningful error messages when necessary. Further, the error message should indicate whether the error happened (Only report the first error the program encounters and exits the program) Here are a few examples: What the user enters Error message 3+2 Expression can't start with a closing parenthesis @ char: 0 Expression can't start with a binary operator @ char: 0 Two binary operators in a row@ char 3 <3+2 3&&&& 5 Two operands in a row @ char 5 15+3 2 A unary operand can't be followed by a binary operator @ char 6 Division by zero @ char 2 10+ 3 1/0

Here is the code I have so far. I'm trying to figure out how to implement a boolean and use precedence. The 2nd expression should be 14 but it comes out as 28 so I'm definitely not understanding.

#include <stack>
#include <iostream>
#include <string>

using namespace std;

// Function to find precedence of

// operators.

int precedence(char op) {

   if (op == '+' || op == '-')

       return 1;

   if (op == '*' || op == '/')

       return 2;
   //if (op == '^' || op == '')
   return 0;

}

// Function to perform arithmetic operations.

int applyOp(int a, int b, char op) {

   switch (op) {

   case '+': return a + b;

   case '-': return a - b;

   case '*': return a * b;

   case '/': return a / b;

   case '^': return a ^ b;

   }

}

// Function that returns value of

// expression after evaluation.

int evaluate(string tokens) {

   int i;

   // stack to store integer values.

   stack <int> values;

   // stack to store operators.

   stack <char> ops;

   for (i = 0; i < tokens.length(); i++) {

       // Current token is a whitespace,

       // skip it.

       if (tokens[i] == ' ')

           continue;

       // Current token is an opening

       // brace, push it to 'ops'

       else if (tokens[i] == '(') {

           ops.push(tokens[i]);

       }

       // Current token is a number, push

       // it to stack for numbers.

       else if (isdigit(tokens[i])) {

           int val = 0;

           // There may be more than one

           // digits in number.

           while (i < tokens.length() &&

               isdigit(tokens[i]))

           {

               val = (val * 10) + (tokens[i] - '0');

               i++;

           }

           values.push(val);

       }

       // Closing brace encountered, solve

       // entire brace.

       else if (tokens[i] == ')')
       {
           while (!ops.empty() && ops.top() != '(')
           {
               int val2 = values.top();
               values.pop();

               int val1 = values.top();
               values.pop();

               char op = ops.top();
               ops.pop();

               values.push(applyOp(val1, val2, op));
           }

           // pop opening brace.
           ops.pop();
       }

       // Current token is an operator.

       else
       {
           // While top of 'ops' has same or greater

           // precedence to current token, which

           // is an operator. Apply operator on top

           // of 'ops' to top two elements in values stack.

           while (!ops.empty() && precedence(ops.top())
               >= precedence(tokens[i])) {

               int val2 = values.top();
               values.pop();

               int val1 = values.top();
               values.pop();

               char op = ops.top();
               ops.pop();

               values.push(applyOp(val1, val2, op));
           }

           // Push current token to 'ops'.

           ops.push(tokens[i]);
       }
   }

   // Entire expression has been parsed at this

   // point, apply remaining ops to remaining

   // values.

   while (!ops.empty()) {

       int val2 = values.top();
       values.pop();

       int val1 = values.top();
       values.pop();

       char op = ops.top();
       ops.pop();

       values.push(applyOp(val1, val2, op));
   }

   // Top of 'values' contains result, return it.

   return values.top();

}

int main() {

   cout << evaluate("1 + 2 * 3") << "\n";

   cout << evaluate("2 + 2 ^ 2 * 12") << "\n";

   //cout << evaluate("1 == 2") << "\n";

   //cout << evaluate("1 + 3 > 2") << "\n";
  
   //cout << evaluate("(4 >= 4) && 0") << "\n";

   //cout << evaluate("(1 + 2) * 3") << "\n";

   //cout << evaluate("++++ 2 - 5 * (3 ^ 2)");

   return 0;

}

Answer 1

#include <bits/stdc++.h>

using namespace std;

  

// Function for finding precedence of

// operators.

int prec(char op){

    if(op == '*'||op == '/')

    return 2;

    if(op == '+'||op == '-')

    return 1;

    return 0;

}

  

// Function used for performing arithmetic operations.

int applyOperation(int a, int b, char op){

    switch(op){

        case '+': return a + b;

        case '-': return a - b;

        case '*': return a * b;

        case '/': return a / b;

    }

}

  

// Function that returns value of

// expression after evaluation.

int eval(string expr){

    int i;

      

    // using a stack to store values(integer).

    stack <int> values;

      

    // stack for storing operators.

    stack <char> ops;

      

    for(i = 0; i < expr.length(); i++){

          

        // Current is a whitespace,

        // skip it.

        if(expr[i] == ' ')

            continue;

          

        // Current character is an opening

        // brace, push it to stack ops that stores operators

        else if(expr[i] == '('){

            ops.push(expr[i]);

        }

          

        // Current character is a number, push

        // it to stack for numbers.

        else if(isdigit(expr[i])){

            int val = 0;

              

            // if more than one digit in one number

            .

            while(i < expr.length() &&

                        isdigit(expr[i]))

            {

                val = (val*10) + (expr[i]-'0');

                i++;

            }

              

            values.push(val);

        }

          

        // Closing brace encountered,now solve the full equation

        else if(expr[i] == ')')

        {

            while(!ops.empty() && ops.top() != '(')

            {

                int val2 = values.top();

                values.pop();

                  

                int val1 = values.top();

                values.pop();

                  

                char op = ops.top();

                ops.pop();

                  

                values.push(applyOp(val1, val2, op));//basically after

//performing the whole operation we push the result onto the stack

            }

              

            // pop opening brace.

            ops.pop();

        }

          

        // Current character is an operator.

        else

        {

            // While top of 'ops' has same or greater

            // precedence to current , which

            // is an operator. Apply operator on top

            // of 'ops' to top two elements in values stack.

            while(!ops.empty() && precedence(ops.top())

                                >= precedence(expr[i])){

                int val2 = values.top();

                values.pop();

                  

                int val1 = values.top();

                values.pop();

                  

                char op = ops.top();

                ops.pop();

                  

                values.push(applyOp(val1, val2, op));

            }

              

            // Push current character to 'ops'.

            ops.push(expr[i]);

        }

    }

      

    // Entire expression has been parsed at this

    // point, apply remaining ops to remaining

    // values.

    while(!ops.empty()){

        int val2 = values.top();

        values.pop();

                  

        int val1 = values.top();

        values.pop();

                  

        char op = ops.top();

        ops.pop();

                  

        values.push(applyOp(val1, val2, op));

    }

      

    // Top of 'values' contains result, return it.

    return values.top();

}