Need help with stack template project for C++ please and thank you. Please send

Question

Need help with stack template project for C++ please and thank you. Please send correctly asnwered code and output screenshot so I do not get confused on making it work and the concepts. The input.txt is in the dropbox link below.

https://www.dropbox.com/sh/36sxpfkktf7rawv/AABiPMaEmnPVSsVlR65Jr7S6a?dl=0

For the last program of the summer, we'll be writing a simple expression evaluator that uses a stack template. We use the usual rules about precedence to resolve which operation should be done first if an expression is potentially ambiguous:

A + B + C // is this (A+B) + C, or A + (B+C)? Addition is left-associative, do A+B first, then add C A – B + C // is this (A-B) + C, or A – (B+C)? Usual rule is left-to-right, do A-B first then add C A + B – C // likewise, this is (A+B) – C A + B*C // Multiplication is higher priority, do B*C first, then add A and so on…

Where it gets fun is when it's something like this: A + B * C / D + E / F * G + H One solution, of course, is to demand that developers remember the exact order of evaluation—if * and / operations are on the same line, is it the * are done then the /, or the / then the *, or left to right? (Answer: different compilers implement it differently, regardless of what the standard says). Thus the usual practical solution is to allow parentheses to allow the developer to specify exactly what is meant: (A + (B * C) / ((D + E) / F) * (G + H)) This has 2 advantages: all compilers follow the “innermost parentheses first” rule and will evaluate the expression the same way, and we can write expressions that would require intermediate variables without them, such as (B*C)/((D+E)/F).

What if the developer didn't fully parenthesize the expression? Then the compiler can insert parentheses, using the rules of the language, and then evaluate the parenthesized expression that results. And yes, that's how it done. Rather than writing code to evaluate a possibly-ambiguous expression, code that inserts characters (parentheses) into a string, and then code to evaluate a fully parenthesized expression, is easier to write, easier to test and debug (because the parts can be tested separately).

For this program we're writing the second part of this: Given a string containing a fully parenthesized algebraic expression, evaluate the expression.

For this program, we'll make a few simplifying assumptions; primarily, all numbers will be single-digit integers >= 0, so they'll be single characters, and the expected results will be integers. (So all operations, including division, will be integer division, with fractions dropped).

So how's this done? To carry this out, 2 stacks are needed, 1 for numbers (ints) and the other for operators (chars). Thus, a template stack is needed. Input is a fully-parenthesized algebraic expression.

The evaluation algorithm is as follows: For each character in the expression: if the character is any of: ( + - * / Push this character on to the operators stack If the character is any of: 0 1 2 3 4 5 6 7 8 9 Convert to an int and push onto the numbers stack (remember that int(‘0’) is NOT the integer 0!) If the character is: ) Pop right operand from numbers stack If the numbers stack is empty, declare an error and end processing of this expression Pop left operand from numbers stack If the numbers stack is empty, declare an error and end processing of this expression Pop operator from operator stack If the operator stack is empty, declare an error and end processing of this expression Carry out operation Push result onto numbers stack Top of operator stack should be the corresponding ( If so, remove it If it's not a left-parenthesis, declare an error and end processing of this expression At end of expression, the following conditions should hold: The operator stack is empty The numbers stack has exactly one value: the value of the expression

You are given an input file containing several expressions, some of them valid, some not. Output is to the screen; for each expression, either the value of the expression or an “invalid expression” message.

Development notes: • Write a template List class. The class should contain the following methods:

push_back(item) push_front(item) insert(item) // assumes list is already sorted, places in order sort() size() clear() pop_front() // removes first item, returns nothing pop_back() // removes last item, returns nothing front() // returns first item, does not alter list back() // returns last item, does not alter list remove(item) // removes 1st occurrence found in list remove_all(item) // removes all occurrences in list is_present(item) const // returns true if item is anywhere in list, false otherwise

As part of the List class, declare a ListException class that can be thrown on a list error (such as attempting to remove something from an empty list, etc) • The stack class will be a wrapper for the list class, exposing only a limited set of of this functionality: push(item), which calls push_back top(), which calls back() pop(), which calls pop_back() size(), clear(), and is_present() all call the corresponding list methods.

• As part of your stack class, define a StackException class that can be thrown on stack overflow or underflow. This can simply be a catch block that catches a ListException and throws a StackException as its action.

• Your program should print error messages for mismatched parentheses (at end of processing a right-parenthesis, the top character on the operator stack is anything other than the corresponding left parenthesis), invalid character in input, or “invalid expression” for anything else.

Example of input and final output should look like this:

Input (input.txt):

(1 + 1)

((7+5)/2) (

(3*4)+ 1)

(1 + * 1)

((7+5)/2))

(((3*4)+ 1)

((7+5)/2 3)

((7$5)/2)

(((9+3)*((3+1)/(1+1)))/4)

Output (to screen):

2

6

13

Mismatched parentheses in expression. Invalid expression.

Stack error in Evaluate(): Stack error on item access Invalid expression.

Invalid expression.

Invalid expression.

Invalid character in input: $ Invalid expression.

6

Press any key to continue . . .

Explanation / Answer

#include #include #define bool int #define false 0 #define true 1 // operators // precedence operators associativity // 4 ! right to left // 3 * / % left to right // 2 + - left to right // 1 = right to left int op_preced(const char c) { switch(c) { case '!': return 4; case '*': case '/': case '%': return 3; case '+': case '-': return 2; case '=': return 1; } return 0; } bool op_left_assoc(const char c) { switch(c) { // left to right case '*': case '/': case '%': case '+': case '-': return true; // right to left case '=': case '!': return false; } return false; } unsigned int op_arg_count(const char c) { switch(c) { case '*': case '/': case '%': case '+': case '-': case '=': return 2; case '!': return 1; default: return c - 'A'; } return 0; } #define is_operator(c) (c == '+' || c == '-' || c == '/' || c == '*' || c == '!' || c == '%' || c == '=') #define is_function(c) (c >= 'A' && c = '0' && c = 'a' && c 0) { sc = stack[sl - 1]; // While there is an operator token, op2, at the top of the stack // op1 is left-associative and its precedence is less than or equal to that of op2, // or op1 has precedence less than that of op2, // Let + and ^ be right associative. // Correct transformation from 1^2+3 is 12^3+ // The differing operator priority decides pop / push // If 2 operators have equal priority then associativity decides. if(is_operator(sc) && ((op_left_assoc(c) && (op_preced(c) 0) { sc = stack[sl - 1]; if(is_function(sc)) { *outpos = sc; ++outpos; sl--; } } } else { printf("Unknown token %c ", c); return false; // Unknown token } } ++strpos; } // When there are no more tokens to read: // While there are still operator tokens in the stack: while(sl > 0) { sc = stack[sl - 1]; if(sc == '(' || sc == ')') { printf("Error: parentheses mismatched "); return false; } *outpos = sc; ++outpos; --sl; } *outpos = 0; // Null terminator return true; } bool execution_order(const char *input) { printf("order: "); const char *strpos = input, *strend = input + strlen(input); char c, res[4]; unsigned int sl = 0, sc, stack[32], rn = 0; // While there are input tokens left while(strpos 1) { printf("%s, ", &sc); } else { printf("%s) ", &sc); } --nargs; } sl-=op_arg_count(c); } else { if(nargs == 1) { sc = stack[sl - 1]; sl--; printf("%c %s; ", c, &sc); } else { sc = stack[sl - 2]; printf("%s %c ", &sc, c); sc = stack[sl - 1]; sl--;sl--; printf("%s; ",&sc); } } // Push the returned results, if any, back onto the stack. stack[sl] = *(unsigned int*)res; ++sl; } ++strpos; } // If there is only one value in the stack // That value is the result of the calculation. if(sl == 1) { sc = stack[sl - 1]; sl--; printf("%s is a result ", &sc); return true; } // If there are more values in the stack // (Error) The user input has too many values. return false; } int main() { // functions: A() B(a) C(a, b), D(a, b, c) ... // identifiers: 0 1 2 3 ... and a b c d e ... // operators: = - + / * % ! const char *input = "a = D(f - b * c + d, !e, g)"; char output[128]; printf("input: %s ", input); if(shunting_yard(input, output)) { printf("output: %s ", output); if(!execution_order(output)) printf(" Invalid input "); } return 0; }

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.