Question

In: Computer Science

C++ OOP Provide a user-friendly way to enter expressions to be evaluated. Please add a comment...

C++ OOP Provide a user-friendly way to enter expressions to be evaluated. Please add a comment explaining each step of your program. Make a program to evaluate infix arithmetic expressions containing integer operands and the operators + (addition), - (subtraction), * (multiplication), / (division) and pairs of parentheses, properly nested. Use the following two-stack algorithm (by E. W. Dijkstra): If the next token in the expression is an integer, push the integer onto the value stack. If the next token in the expression is an operator, If the operator stack is empty or the priority of the operator is greater than the priority of the operator at the top of the operator stack, push the operator onto the operator stack. Otherwise pop an operator and two integers; push the result of applying that operator to those integers onto the value stack. Then decide again what to do with the operator at the next token. If the token in the expression is a left parenthesis, push it onto the operator stack. If the next token in the expression is a right parenthesis: pop an operator and two integers; push the result of applying that operator to those integers onto the value stack. Continue until the top of the operator stack is a left parenthesis. Then pop the left parenthesis and ignore the right parenthesis. At the end of the expression, operators are popped off and evaluated (popping the operands and pushing the results) until the operator stack is empty At this point, the operand stack should have exactly one number in it – the result of the evaluation of the expression.

Solutions

Expert Solution


#include <bits/stdc++.h>
using namespace std;
 
// Function to find precedence of 
// operators.
int precedence(char op){
    if(op == '+'||op == '-')
    return 1;
    if(op == '*'||op == '/')
    return 2;
    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;
    }
}
 
// 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);
             
            // right now the i points to 
            // the character next to the digit,
            // since the for loop also increases 
            // the i, we would skip one 
            //  token position; we need to 
            // decrease the value of i by 1 to
            // correct the offset.
              i--;
        }
         
        // 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.
            if(!ops.empty())
               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("10 + 2 * 6") << "\n";
    cout << evaluate("100 * 2 + 12") << "\n";
    cout << evaluate("100 * ( 2 + 12 )") << "\n";
    cout << evaluate("100 * ( 2 + 12 ) / 14");
    return 0;
}

OUTPUT:

22
212
1400
100

Related Solutions

used in python3 please add comment , thank you Shopping Bag: Assume the user has a...
used in python3 please add comment , thank you Shopping Bag: Assume the user has a bunch of purchases they would like to make. They enter the price of each item, and the quantity and they want to add it to their cart. They tell us if they have more items to purchase, and if they do, we repeat getting the data and add the cost to the shopping bag. When they're done, we display the total. We will not...
C++ OOP Make a program to evaluate infix arithmetic expressions containing integer operands and the operators...
C++ OOP Make a program to evaluate infix arithmetic expressions containing integer operands and the operators + (addition), - (subtraction), * (multiplication), / (division) and pairs of parentheses, properly nested. Use the following two-stack algorithm (by E. W. Dijkstra): If the next token in the expression is an integer, push the integer onto the value stack. If the next token in the expression is an operator, If the operator stack is empty or the priority of the operator is greater...
(C++ program) ***User Interface Write a program that offers an easy way to add items, remove...
(C++ program) ***User Interface Write a program that offers an easy way to add items, remove the last item, look at the last item put in the list. You will write all of the code for processing the stack - do not use any predefined objects in C++.  You decide how the interface will look. A menu driven program is always a good choice. ***Rules for program*** NEVER use break, exit, return, pass, continue or anything to leave a loop (or...
This code needs to be in C++, please. Step 1: Add code to prompt the user...
This code needs to be in C++, please. Step 1: Add code to prompt the user to enter the name of the room that they are entering information for. Validate the input of the name of the room so that an error is shown if the user does not enter a name for the room. The user must be given an unlimited amount of attempts to enter a name for the room. Step 2: Add Input Validation to the code...
Write in C# please! Ask the user to enter all of their exam grades. Once they...
Write in C# please! Ask the user to enter all of their exam grades. Once they are done, calculate the minimum score, the maximum score and the average score for all of their scores. Perform this using at least 2 Loops (can be the same type of loop) and not any built in functions.
C code please (1) Prompt the user to enter a string of their choosing. Store the...
C code please (1) Prompt the user to enter a string of their choosing. Store the text in a string. Output the string. (1 pt) Ex: Enter a sample text: we'll continue our quest in space. there will be more shuttle flights and more shuttle crews and, yes, more volunteers, more civilians, more teachers in space. nothing ends here; our hopes and our journeys continue! You entered: we'll continue our quest in space. there will be more shuttle flights and...
Please code C# 8. Write a program that prompts the user to enter an integer. The...
Please code C# 8. Write a program that prompts the user to enter an integer. The program then determines and displays the following: Whether the integer is divisible by 5 and 6 Whether the integer is divisible by 5 or 6
// Add the following functions: // 1. 'getRadius' asks the user to enter the radius of...
// Add the following functions: // 1. 'getRadius' asks the user to enter the radius of a circle // and returns the given value. (should return a double) // 2. 'calcArea' takes the radius and returns the area of a circle. // 3. 'printResults' void type function that should print the results to // console. // Your function needs to have a local variable called 'PI' which holds the // value '3.14159'. // The function call is provided, you just...
C++ please show the error mesg if user enter others letter insated of I and O...
C++ please show the error mesg if user enter others letter insated of I and O and also numbers must be greater than 0 if user input -, show the error mesg untill user out the correct...thanks please Overloaded Hospital Write a program that computes and displays the charges for a patient’s hospital stay. First, the program should ask if the patient was admitted as an in-patient or an out-patient. Please keep asking the user until the user enters the...
Assignment in C: prompt the user to enter secret message that is terminated by presding Enter....
Assignment in C: prompt the user to enter secret message that is terminated by presding Enter. You can assume that the the length of this message will be less than 100 characters. You will then parae this message, character by character, converting them to lower case, and find corresponding characters in the words found in the key text word array. Once a character match is found, you will write the index of the word and the index of the character...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT