Question

In: Computer Science

C++ program that can take in EITHER "infix" or "prefix" (NOT POSTFIX) and transforms it into...

C++ program that can take in EITHER "infix" or "prefix" (NOT POSTFIX) and transforms it into the other one. Should use stack and have infixToPrefix and prefixToInfix functions with a simple main function for execution.

Solutions

Expert Solution

(*Note: Please up-vote. If any doubt, please let me know in the comments)

C++ CODE:

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;


bool
isOperator (char x)
{
switch (x)
{
case '+':
case '-':
case '/':
case '*':
return true; //return true if character is an operator, false otherwise
}
return false;
}

int
precedence (char C) //To return precedence as an integer
{
if (C == '-' || C == '+')
return 1;
else if (C == '*' || C == '/')
return 2;
else if (C == '^')
return 3;
return 0;
}

string
infixToPrefix (string infix)
{
string prefix;
stack < char >s;
reverse (infix.begin (), infix.end ());

for (int i = 0; i < infix.length (); i++)
{
if (infix[i] == '(')
   {
   infix[i] = ')';
   }
else if (infix[i] == ')')
   {
   infix[i] = '(';
   }
}
for (int i = 0; i < infix.length (); i++)
{
if ((infix[i] >= 'a' && infix[i] <= 'z')
   || (infix[i] >= 'A' && infix[i] <= 'Z'))
   {
   prefix += infix[i];
   }
else if (infix[i] == '(')
   {
   s.push (infix[i]);
   }
else if (infix[i] == ')')
   {
   while ((s.top () != '(') && (!s.empty ()))
   {
   prefix += s.top ();
   s.pop ();
   }

   if (s.top () == '(')
   {
   s.pop ();
   }
   }
else if (isOperator (infix[i]))
   {
   if (s.empty ())
   {
   s.push (infix[i]);
   }
   else
   {
   if (precedence (infix[i]) > precedence (s.top ()))
       {
       s.push (infix[i]);
       }
   else if ((precedence (infix[i]) == precedence (s.top ()))
       && (infix[i] == '^'))
       {
       while ((precedence (infix[i]) == precedence (s.top ()))
           && (infix[i] == '^'))
       {
       prefix += s.top ();
       s.pop ();
       }
       s.push (infix[i]);
       }
   else if (precedence (infix[i]) == precedence (s.top ()))
       {
       s.push (infix[i]);
       }
   else
       {
       while ((!s.empty ())
           && (precedence (infix[i]) < precedence (s.top ())))
       {
       prefix += s.top ();
       s.pop ();
       }
       s.push (infix[i]);
       }
   }
   }
}

while (!s.empty ())
{
prefix += s.top ();
s.pop ();
}

reverse (prefix.begin (), prefix.end ());
return prefix;
}

string
prefixToInfix (string pre_exp)
{
stack < string > s;

  
int length = pre_exp.size ();

  
for (int i = length - 1; i >= 0; i--)
{

  
if (isOperator (pre_exp[i]))
   {

  
   string op1 = s.top ();
   s.pop ();
   string op2 = s.top ();
   s.pop ();

   // concatenate the operands from stack and the currently read operator
   string temp = "(" + op1 + pre_exp[i] + op2 + ")";

   // Push temp to stack
   s.push (temp);
   }

// when symbol is not any operator
else
   {

   // push the operand on stack
   s.push (string (1, pre_exp[i]));
   }
}


return s.top ();
}


int
main ()
{
//string pre = "*+A/BC-/ADE", inf = "(A+B/C)*(A/D-E)";
string pre, inf;
int choice;
cout << "Enter your choice (1 or 2): " << endl;
cout << "1. Convert Infix to Prefix" << endl << "2. Convert Prefix to Infix"
<< endl;
cin >> choice;
switch (choice)
{
case 1:
cout << "Enter an Infix Expression" << endl;
cin >> inf;
cout << "Prefix expression : " << infixToPrefix (inf) << endl;
break;
case 2:
cout << "Enter a Prefix Expression" << endl;
cin >> pre;
cout << "Infix expression : " << prefixToInfix (pre);
break;
}

return 0;
}

OUTPUT SCREENSHOTS:


Related Solutions

An arithmetic expression can be represented in three different formats: infix, prefix, and postfix. In the...
An arithmetic expression can be represented in three different formats: infix, prefix, and postfix. In the infix notation, the operator comes between two operands. In the postfix notation, the operator comes after its two operands. For example, an expression a/b can be transformed to ab/. The following are some examples of the postfix expressions: 2+6*4 Its postfix notation is 2 6 4 * + 2-3+5/4*9-1 Its postfix expression is 2 3 – 5 4 / 9 * + 1 -...
Write a program that converts prefix expressions to postfix and postfix expressions to prefix. (java) The...
Write a program that converts prefix expressions to postfix and postfix expressions to prefix. (java) The program for this project should consist of three classes. -The main class should create a GUI that allows the user to input an expression in either prefix or postfix and convert it to postfix or prefix, respectively. -The other class should contain the code to perform the conversions. --->The pseudocode for prefix to postfix, which requires two stacks, is shown below: tokenize the string...
C++ Data Structure Write a program to change following infix expressions to postfix expressions using a...
C++ Data Structure Write a program to change following infix expressions to postfix expressions using a stack a) D-B+C b) C*D+A*B c) (A*B)*C+D*F-C d) (A-4*(B-C)-D/E)*F
Write a program that takes an infix expression as input and produces a postfix expression. The...
Write a program that takes an infix expression as input and produces a postfix expression. The infix and postfix expressions are in the form of vectors of strings. We will test with a main method that takes a file name as input from the command line. We will test your implementation using printPostFix() method.   There are sample input and output files in this folder. You may edit the header file. Example 1 infix expression = apple + banana * cat...
Using java.util.Stack and java.util.StringTokenizer to write a program that converts an infix expression to a postfix...
Using java.util.Stack and java.util.StringTokenizer to write a program that converts an infix expression to a postfix expression using data from infix.dat. Make sure your program can handle negative number. If the input expression can’t be converted, display error message.(1.5 points) (Should remove parentheses) infix.dat 5 * 6 + -10 3 - 2 + 4 7 ( 3 * 4 - (2 + 5)) * 4 / 2 10 + 6 * 11 -(3 * 2 + 14) / 2 2...
Implement an infix expression to postfix expression convertor in C++. Note: - Support +, -, *,...
Implement an infix expression to postfix expression convertor in C++. Note: - Support +, -, *, /, ( and ) in infix expressions. - Operands will be nonnegative only. - Assume infix expressions are valid and well formatted (one blank space to separate operand/operator) For example, - 3 * 4 + 5 ➔ 3 4 * 5 + - 3 + 4 * 5 ➔ 3 4 5 * + - (3 + 4) * (5 + 6) ➔ 3...
Using a stack, write a program that turns a simple infix arithmetic expression into a postfix...
Using a stack, write a program that turns a simple infix arithmetic expression into a postfix expression. For example, 1 + 2 * 3 becomes 2 3 * 1 +. Also, evaluate the expression to ensure the expression is correct.
Hi there, I am making a program using trees, and recursion to compute prefix, infix, and...
Hi there, I am making a program using trees, and recursion to compute prefix, infix, and postfix expressions. I am struggling with placing parentheses to separate the infix numbers, and with how I should write my evaluation. (In java) if someone could please help me out. I included my evaluation class, and my current output. public class Evaluation { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter a prefix expression:"); Node root = buildTree(sc); System.out.println("Infix expression:");...
* the Algorithm: * write a java program to convert infix to postfix create(OpStk) OpStk.push("#") token...
* the Algorithm: * write a java program to convert infix to postfix create(OpStk) OpStk.push("#") token = nextToken() while (token != "#") if (token is an operand) append token to postfix expression else if (token is "(") // Left paren - Start of sub-expr OpStk.push( token ) else if (token is ")") // Right paren - End of sub-expr pop operators off the stack and append to the postfix expression - stop when you've popped a "(" else (token is...
Write a java class program to convert from INFIX TO POSTFIX Using stack operations
Write a java class program to convert from INFIX TO POSTFIX Using stack operations
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT