Question

Polish notation, also known as Polish prefix notation or simply prefix notation, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left of their operands.

The expression for adding the numbers 1 and 2, in prefix notation, is written as “+ 12” rather than “1 + 2”. In more complex expressions, the operands may be nontrivial expressions including operators of their own. For instance, the expression that would be written in conventional infix notation as (5 + 6) * 7 can be written in prefix as * (+ 5 6) 7

In this assignment, we only care about binary operators: + - * and /.

For binary operators, prefix representation is unambiguous and bracketing the prefix expression is unnecessary. As such, the previous expression can be further simplified to * + 5 6 7

The processing of the product is deferred until its two operands are available (i.e., 5 plus 6, then multiplies the result with 7). As with any notation, the innermost expressions are evaluated first, but in prefix notation this ”innermost-ness” is conveyed by order rather than bracketing.

Your task is to create a class that convert a prefix expression to a standard form (otherwise known as infix) and compute the prefix expression.

Main function

The test script will compile your code using

g++ -o main.out -std=c++11 -O2 -Wall *.cpp

It is your responsibility to ensure that your code compiles on the university system. g++ has too many versions, so being able to compile on your laptop does not guarantee that it compiles on the university system. You are encouraged to debug your code on a lab computer (or use SSH).

Create a main function that takes in one line. The line contains a list of operators and operands separated by spaces. The input doesn’t contain parenthesis. An operator is a character from +, -, *, and /. An operand is a nonnegative integer from 0 to 99. You are asked to convert the prefix expression to an infix form and output its value as well. If the expression is not a valid prefix expression, your program should output “Error”.

Sample input: * - 5 6 7

Sample output: (5 - 6) * 7 = -7

  

Sample input: * 5

Sample output: Error

Sample input: * 5 6 7

Sample output: Error

Please provide the .h, .cpp and main.cpp file for this, like Polish.h Polish.cpp and main.cpp thank you

Answer 1

The logic is defined in the program comments on every important line.

CODE:

Polish.h

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

using namespace std;

string convertPrefixToInfix(string prefixExpression);

Polish.cpp

#include "Polish.h"

// Convert prefix to Infix expression
string convertPrefixToInfix(string prefixExpression)
{
   stack<string> infixStack;   // infix expression
   stack<long> evalStack;       // result of the infix expression
   char ch;
   string operand = "";
   long result = 0;

   // length of prefix expression
   int length = prefixExpression.size();

   // parse expression from end to start that is right to left
   for (int index = length - 1; index >= 0; index--)
   {
       ch = prefixExpression[index];
       if (ch == ' ' && !operand.empty())
       {
           infixStack.push(operand);
           evalStack.push(atol(operand.c_str()));
           operand = "";
           continue;
       }
       // if the read character is operator,
       // get top 2 values from the stack and pop them
       else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
       {
           // make sure there are enough operands on the stacks.
           // there should be atleast 2 operand on the stack.
           // if not expression is not valid. retun Error.
           if (infixStack.size() < 2)
           {
               return "Error";
           }

           // retrieve first operand from top of the stack
           string op1 = infixStack.top();
           infixStack.pop();

           // retrieve second operand from top of the stack
           string op2 = infixStack.top();
           infixStack.pop();

           // make the infix expression
           string temp = "(" + op1 + prefixExpression[index] + op2 + ")";

           // evaluate the expression
           // pop first operand value
           long op1Value = evalStack.top();
           evalStack.pop();

           // pop second operand value
           long op2Value = evalStack.top();
           evalStack.pop();

           // perform the operation and push the result on stack
           if (ch == '+')
               evalStack.push(op1Value + op2Value);
           else if (ch == '-')
               evalStack.push(op1Value - op2Value);
           else if (ch == '*')
               evalStack.push(op1Value * op2Value);
           else if (ch == '/')
               evalStack.push(op1Value / op2Value);

           // push the formed infix expression on the stack
           infixStack.push(temp);
       }
       // if character is an operand, simply push it on the stack as string
       else
       {
           operand += string(1, prefixExpression[index]);
       }
   }

   if (infixStack.size() > 1)
   {
       return "Error";
   }

   // at this point, the top of the stack would have the infix expression,
   // return it.
   return infixStack.top() + " = " + to_string(evalStack.top());
}
Main.cpp

#include "Polish.h"
int main()
{
   string prefixExpression;

   // prompt user for input
   cout << "Input prefix expression: ";
   getline(cin, prefixExpression);

   // call the convertPrefixToInfix function and display the infix expression
   cout << "Infix : " << convertPrefixToInfix(prefixExpression);

   return 0;
}

OUTPUT: