Converting Infix to Postfix Expressions

Infix and Postfix notations are two different but equivalent ways of writing expressions. It is easiest to demonstrate the differences by looking at examples of operators that take two operands.

Infix notation: X + Y

Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer." Infix notation needs extra information to make the order of evaluation of the operators clear: rules built into the language about operator precedence and associativity, and brackets ( ) to allow users to override these rules. For example, the usual rules for associativity say that we perform operations from left to right, so the multiplication by A is assumed to come before the division by D. Similarly, the usual rules for precedence say that we perform multiplication and division before we perform addition and subtraction.

Postfix notation (also known as "Reverse Polish notation"): X Y +

Operators are written after their operands. The infix expression given above is equivalent to A B C + * D / The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. Because the "+" is to the left of the "*" in the example above, the addition must be performed before the multiplication. Operators act on values immediately to the left of them. For example, the "+" above uses the "B" and "C". We can add (totally unnecessary) brackets to make this explicit: ( (A (B C +) ) D /) Thus, the "" uses the two values immediately preceding: "A", and the result of the addition. Similarly, the "/" uses the result of the multiplication and the "D".

Goals:

The goal of this assignment is to gain familiarity working with stacks and implementing good class design (proper use of const, and access specifiers). Problem 9 from Chapter 7 (p. 449) has been slightly modified as follows.

Requirements:

Design a class named Infix that stores the infix and postfix strings Remember to carefully consider the use of const and access specifiers. Your class will need to handle +, -, *, /, and ^ (exponentiation). You may assume that the expressions you will process are error free. The class must include the following public operations:

• void setInfix(std::string) stores the infix expression, and updates the postfix expression.
• std::string getInfix() retrieves the infix expression
• std::string getPostfix() retrieves the postfix expression
• int getNumberOfOperators() returns the number of operators contained in the expression
• int getNumberOfOperands() returns the number of operands contained in the expression
• void clear() resets the infix/postfix expression to an empty string
• Infix(std::string ) constructor takes a string parameter as an infix expression, stores the infix expression and sets the postfix expression.
• Default constructor stores an empty infix/postfix expression

You may find it useful to include these additional functions:

• convertToPostfix Converts the infix expression into a postfix expression. The resulting postfix expression is stored in pfx.
• bool precedence Determines the precedence between two operator parameters. If the first operator is of higher or equal precedence than the second operator, it returns the value true; otherwise, it returns the value false.

You may use the STL stack class or your own stack implementation.

Helpful Hints:

The following process can be used to convert an infix expression to a postfix expression. Suppose infx is a string that represents the infix expression and pfx is a string that represents the postfix expression. The rules to convert infx to pfx are as follows:

1. Initialize pfx to an empty string and also initialize the stack.

2. Get the next symbol from infx and store it in a string called sym. (Note that a symbol could be an operator, a parenthesis (left or right), a single digit, or an entire number. For example, if infx is "123 + 456", then the first symbol is 123, not 1. The second symbol is a + character. The third symbol is 456. Whitespaces of any kind are not symbols.)

   • If sym is an operand (i.e. a number), append sym to pfx.

   • If sym is '(', push sym into the stack.

   • If sym is ')', pop and append all the symbols from the stack until the most recent left parenthesis. Pop and discard the left parenthesis.

   • If sym is an operator (i.e. '+', '-', '*', '/', '^'):

     • Pop and append all the operations from the stack to pfx that are above the most recent left parenthesis and have precedence greater than or equal to sym.
     • Push sym onto the stack.

3. After processing infx, some operators might be left in the stack. Pop and append to pfx everything from the stack.

Standard precedence for arithmetic operators:

1. exponents
2. multiplication and division
3. addition and subtraction

Infix.h

/* Place your Infix class declaration here */

Infix.cpp

#include "Infix.h"

/* Place your Infix class implementation here */

InfixTest.cpp

#include #include #include #include #include

#include "Infix.h"

using namespace std;

//This helps with testing, do not modify. bool checkTest(string testName, string whatItShouldBe, string whatItIs) {

//get rid of spaces whatItIs.erase(whatItIs.begin(), std::find_if(whatItIs.begin(), whatItIs.end(), std::not1(std::ptr_fun(std::isspace)))); whatItIs.erase(std::find_if(whatItIs.rbegin(), whatItIs.rend(), std::not1(std::ptr_fun(std::isspace))).base(), whatItIs.end());

if (whatItShouldBe == whatItIs) { cout << "Passed test " << testName << " *** Output was \""<< whatItIs << "\"" << endl; return true; } else { if (whatItShouldBe == "") { cout << "***Failed test " << testName << " *** " << endl << " Output was \""<< whatItIs << "\"" << endl << " Output should have been blank. " << endl; } else { cout << "***Failed test " << testName << " *** " << endl << " Output was \""<< whatItIs << "\"" << endl << " Output should have been \"" << whatItShouldBe << "\"" << endl; } return false; } }

//This helps with testing, do not modify. bool checkTest(string testName, int whatItShouldBe, int whatItIs) {

if (whatItShouldBe == whatItIs) { cout << "Passed test " << testName << " *** Output was \""<< whatItIs << "\"" << endl; return true; } else { cout << "***Failed test " << testName << " *** " << endl << " Output was \""<< whatItIs << "\"" << endl << " Output should have been \"" << whatItShouldBe << "\"" << endl; return false; } }

int main() {

//Test Default Constructor Infix myInfix; checkTest("Test #1", "", myInfix.getInfix()); checkTest("Test #2", "", myInfix.getPostfix()); checkTest("Test #3", 0, myInfix.getNumberOfOperands()); checkTest("Test #4", 0, myInfix.getNumberOfOperators());

//SetInfix string expression = "(2+3)"; myInfix.setInfix(expression); checkTest("Test #5", "(2+3)", myInfix.getInfix()); checkTest("Test #6", 2, myInfix.getNumberOfOperands()); checkTest("Test #7", 1, myInfix.getNumberOfOperators()); checkTest("Test #8", "2 3 +", myInfix.getPostfix());

//Clear myInfix.clear(); checkTest("Test #9", "", myInfix.getInfix()); checkTest("Test #10", "", myInfix.getPostfix()); checkTest("Test #11", 0, myInfix.getNumberOfOperands()); checkTest("Test #12", 0, myInfix.getNumberOfOperators());

//Lots More Expression expression = "2+3"; myInfix.setInfix(expression); checkTest("Test #13", "2 3 +", myInfix.getPostfix()); checkTest("Test #14", 2, myInfix.getNumberOfOperands());

expression = "(123+456)"; myInfix.setInfix(expression); checkTest("Test #15", "123 456 +", myInfix.getPostfix());

expression = "(8-5)"; myInfix.setInfix(expression); checkTest("Test #16", "8 5 -", myInfix.getPostfix());

expression = "((3-4)-5)"; myInfix.setInfix(expression); checkTest("Test #17", "3 4 - 5 -", myInfix.getPostfix()); checkTest("Test #18", 2, myInfix.getNumberOfOperators());

expression = "(3 - (4 - 5))"; myInfix.setInfix(expression); checkTest("Test #19", "3 4 5 - -", myInfix.getPostfix());

expression = "(3*(8/2))"; myInfix.setInfix(expression); checkTest("Test #20", "3 8 2 / *", myInfix.getPostfix()); checkTest("Test #21", 3, myInfix.getNumberOfOperands());

expression = "3 + 8 / 2"; myInfix.setInfix(expression); checkTest("Test #22", "3 8 2 / +", myInfix.getPostfix());

expression = "24 / 3 + 2"; myInfix.setInfix(expression); checkTest("Test #23", "24 3 / 2 +", myInfix.getPostfix());

expression = "((1 + 2) * (3 + 4))"; myInfix.setInfix(expression); checkTest("Test #24", "1 2 + 3 4 + *", myInfix.getPostfix());

expression = "2^3"; myInfix.setInfix(expression); checkTest("Test #25", "2 3 ^", myInfix.getPostfix());

expression = "8 + 3^4"; myInfix.setInfix(expression); checkTest("Test #26", "8 3 4 ^ +", myInfix.getPostfix());

expression = "5 ^ 6 - 9"; myInfix.setInfix(expression); checkTest("Test #27", "5 6 ^ 9 -", myInfix.getPostfix());

expression = "5 ^ (8 * 4)"; myInfix.setInfix(expression); checkTest("Test #28", "5 8 4 * ^", myInfix.getPostfix());

expression = "(4 + 3) * (7 ^56)"; myInfix.setInfix(expression); checkTest("Test #29", "4 3 + 7 56 ^ *", myInfix.getPostfix()); checkTest("Test #30", 3, myInfix.getNumberOfOperators());

expression = "1999 ^ 9991"; myInfix.setInfix(expression); checkTest("Test #31", "1999 9991 ^", myInfix.getPostfix());

expression = "5 ^ 4 ^ 7 + 9"; myInfix.setInfix(expression); checkTest("Test #32", "5 4 ^ 7 ^ 9 +", myInfix.getPostfix());

expression = "55 ^ (667 ^ 32) * 89"; myInfix.setInfix(expression); checkTest("Test #33", "55 667 32 ^ ^ 89 *", myInfix.getPostfix()); checkTest("Test #34", 4, myInfix.getNumberOfOperands());

expression = "(((3+12)-7)*120)/(2+3)"; myInfix.setInfix(expression); checkTest("Test #35", "3 12 + 7 - 120 * 2 3 + /", myInfix.getPostfix());

expression = "((((9+(2*(110-(20/2))))*8)+1000)/2)-((400*2500)-1000001)"; myInfix.setInfix(expression); checkTest("Test #36", "9 2 110 20 2 / - * + 8 * 1000 + 2 / 400 2500 * 1000001 - -", myInfix.getPostfix()); checkTest("Test #37", 10, myInfix.getNumberOfOperators()); checkTest("Test #38", 11, myInfix.getNumberOfOperands());

//Infix String Constructors myInfix = Infix(""); checkTest("Test #39", "", myInfix.getInfix()); checkTest("Test #40", "", myInfix.getPostfix()); checkTest("Test #41", 0, myInfix.getNumberOfOperands()); checkTest("Test #42", 0, myInfix.getNumberOfOperators());

myInfix = Infix("2 + 3"); checkTest("Test #43", "2 + 3", myInfix.getInfix()); checkTest("Test #44", "2 3 +", myInfix.getPostfix()); checkTest("Test #45", 1, myInfix.getNumberOfOperators()); checkTest("Test #46", 2, myInfix.getNumberOfOperands());

myInfix = Infix("(2 + 3)"); checkTest("Test #47", "2 3 +", myInfix.getPostfix());

myInfix = Infix("123 + 456"); checkTest("Test #48", "123 456 +", myInfix.getPostfix());

myInfix = Infix("8 - 5"); checkTest("Test #49", "8 5 -", myInfix.getPostfix());

myInfix = Infix("3 - 4 - 5"); checkTest("Test #50", "3 4 - 5 -", myInfix.getPostfix());

myInfix = Infix("3 - (4 - 5)"); checkTest("Test #51", "3 4 5 - -", myInfix.getPostfix()); checkTest("Test #52", "3 - (4 - 5)", myInfix.getInfix()); checkTest("Test #53", 2, myInfix.getNumberOfOperators()); checkTest("Test #54", 3, myInfix.getNumberOfOperands());

return 0; }