- Please Follow The Instructions Below And Include My Process To Make The Program Work Please Include My Process Below An 1 (112.61 KiB) Viewed 10 times
- Please Follow The Instructions Below And Include My Process To Make The Program Work Please Include My Process Below An 2 (87.18 KiB) Viewed 10 times
using namespace std;
// Function infix2Postfix accepts an infix expression andconverts to the// equivalent postfix expression. The postfix expression is writtento// ostream out.void infix2Postfix(string infix, ostream& out){}
// Function hasPrecedenceGreaterThanOrEqualTo accepts twocharacter// parameters, each representing an arithmetic operator (+, -, *,/).// The function returns true if operator1 has precedence greaterthan // or equal to operator2 and false otherwise.bool hasPrecedenceGreaterThanOrEqualTo(char operator1, charoperator2){}
This problem requires you to write a function to convert an infix expression to postfix format. The evaluation of an infix expression such as A + B C requires knowledge of which of the two operations, + or *, should be performed first. In general, A + B + C is to be interpreted as A + (B+C) unless otherwise specified. We say that multiplication takes precedence over addition. Suppose that we would now like to convert A + B + C to postfix. Applying the rules of precedence, we begin by converting the first portion of the expression that is evaluated, namely the multiplication operation. Doing this conversion in stages, we obtain A + B * C A + BC. A B C * + Given infix form Convert the multiplication Convert the addition The major rules to remember during the conversion process are that the operations with highest prece- dence are converted first and that after a portion of an expression has been converted to postfix it is to be treated as a single operand. Let us now consider the same example with the precedence of operators reversed by the deliberate insertion of parentheses: (A + B) C A B + C A B + C * Given infix form Convert the addition Convert the multiplication Note that in the conversion from "A B + * C" to "A B + C *", "A B+" was treated as a single operand. The rules for converting from infix to postfix are simple, provided that you know the order of precedence. We consider four binary operations: addition, subtraction, multiplication, and division. These oper- ations are denoted by the usual operators, +, -, *, and /, respectively. There are two levels of operator precedence. Both * and / have higher precedence than + and -. Furthermore, when unparenthesized opera- tors of the same precedence are scanned, the order is assumed to be left to right. Parentheses may be used in infix expressions to override the default precedence. The postfix form requires no parentheses. The order of the operators in the postfix expressions deter- mines the actual order of operations in evaluating the expression, making the use of parentheses unnecessary. Write a function to convert an infix expression to its equivalent postfix expression. The function will receive two arguments: a string containing the infix expression and an output stream where the output is to be written. You may assume that the infix expression is error-free. An arbitrary number of whitespace characters may occur between any two symbols in an expression. A symbol may be an operand (a single uppercase letter), an operator (+,-, *, or /), a left parenthesis, or a right parenthesis. Your function should write the equivalent postfix expression to the given output stream. The output should be formatted as shown below. Write a second function that will receive two character arguments, each representing an operator (+,-, *, or /). The function returns true if the first operator has precedence greater than or equal to the second operator and false otherwise.
I. Pseudocode for converting an infix expression to a postfix expression A. Initialize a stack of characters to hold the operator symbols and parentheses. B. do 1. if the next input is whitespace a) continue 2. else if the next input is a left parenthesis a) read the left parenthesis and push it onto the stack. 3. else if the next input is an operand a) read the operand and write it to the output. 4. else if the next input is an operator a) while (1) The stack is not empty, and (2) The next symbol on the stack is not a left parenthesis, and (3) The next symbol on the stack is an operator with precedence greater than or equal to the next input symbol b) do (1) Print the top operator and pop it c) When the above loop terminates, read the next input symbol, and push this symbol onto the stack. 5. else a) Read and discard the next input symbol (which should be a right parenthesis). Print the top operation and pop it; keep printing and popping until the next symbol on the stack is a left parenthesis. (If no left parenthesis is encountered, then print an error message indicating unbalanced parentheses, and halt.) Finally, pop the left parenthesis. C. while there is more of the expression to process D. Print and pop any remaining operations on the stack. (There should be no remaining left paren- theses; otherwise, the input expression did not have balanced parentheses.) A sample main function for testing your function is shown in Figure 1. Commands to compile, link, and run this assignment are shown in Figure 2. To use the Makefile as distributed in class, add a target of lab41 to targets2srcfiles.
1 #include <iostream> 2 #include <cstdlib> #include <string> 4 5 using namespace std; 6 7 // Function infix2Postfix accepts an infix expression and converts to the s // equivalent postfix expression. The postfix expression is written to 9 // ostream out. 10 void infix2Postfix (string infix, ostream& out); 11 12 // Function hasPrecedenceGreaterThanOrEqualTo accepts two character 13 // parameters, each representing an arithmetic operator (+,-, *, /). 14 // The function returns true if operatori has precedence greater than 15 // or equal to operator2 and false otherwise. bool hasPrecedenceGreaterThanDrEqualTo (char operatori, char operator2); 16 17 18 19 20 21 22 24 26 27 28 29 30 31 int main() { } string infix; while (getline (cin, infix)) { } cout << "Infix: " << infix << endl; cout << "Postfix: "; infix2Postfix(infix, cout); cout << endl; return EXIT_SUCCESS;
1 newuser@csunix "> cd 2336 newuser@csunix /2336> ./getlab.ksh 41 * Checking to see if a folder exists for Lab 41. . .No Creating a folder for Lab 41 4 5 6 7 9 10 11 12 13 14 15 18 19 20 newuser@csunix /2336> cd 41 16 newuser@csunix /2336/41> 18 17 01.dat 21 * Checking to see if Lab 41 has sample input and output files. Yes Copying input and output files for Lab 41 from folder /usr/local/2336/data/41 to folder ./41 *Checking to see if /usr/local/2336/src/lab41main. C exists. . .Yes /usr/local/2336/src/lab41main. C to folder ./41 Copying file * Checking to see if /usr/local/2336/include/lab41.h exists...No Makefile newuser@csunix /2336/41> make lab41 g++ -g -Wall-std-c++11 -c lab4imain.C -I/usr/local/2336/include -I. g++ -g -Wall -std-c++11 -c lab41.cpp -1/usr/local/2336/include -I. g++ -o lab41 lab4imain.o lab41.o -L/usr/local/2336/lib-lm-lbits 22 newuser@csunix /2336/41> cat 01.dat 33 * Copying file /usr/local/2336/src/Makefile to folder ./41 Adding a target of lab41 to targets2srcfiles Touching file ./41/lab41.cpp 35 36 Edit file/41/lab41.cpp in Notepad++ 01.out A+B-C 24 A + B C 25 (A + B) / (CD) 26 ((A+B) (C - D ) + E) 45 46 27 A+B+(C-D)-E 28 ((A)) 29 A/B + (CD) E 30 A/B + C + D - E 31 newuser@csunix /2336/41> cat 01.dat ./lab41 32 Infix: A+B-C Postfix: A B + C - Infix: A + B C Postfix: A B C + Infix: Postfix: A B + CD-/ (A + B ) / (C-D) 37 38 Infix: 39 Postfix: A B C D (CA+ B) 40 Infix: A+B+(C-D)-E 1ab41.cpp lab41main.C (C E + FG+ / Postfix: A B C D E- Infix: ((A)) Postfix: A Infix: A / B (C+ D) E Postfix: A B/CD++ E- Infix: A/B + C + D E Postfix: A B / C + D + E- / (FG) D) + E) 1 newuser@csunix /2336/41> cat 01.dat ./lab41 > my.out 49 newuser@csunix /2336/41> diff 01.out my.out 50 newuser@csunix -/2336/41> (F + G)