I\'m stuck on an assignment using a stack to covert a prefix or postfix equation
ID: 3711084 • Letter: I
Question
I'm stuck on an assignment using a stack to covert a prefix or postfix equation to infix. The example that we're given is to covert something like ++a*bcd or abc*+d+ to infix notation. If I were working with actual numbers then I would've been able to do this without any problems (I think). The way I'm trying to do it forces me to pop chars off of the stack and then push a string back onto the stack. I've tried serveral different ways to work around this issue but none have worked. Please help! This is my code (I went through and put in spaces to try to make it more readable but they all disappeared when I posted):
#include
#include
#include
typedef struct char_node{
char input;
struct char_node *next;
} char_node;
typedef struct{
char_node *s_top;
} char_stack;
void push(char_stack *sPtr, char newChar);
char pop(char_stack *sPtr);
char* rev_string(char *str);
int main()
{
char *usr_in;
char temp_str[3];
char operator;
char var1;
char var2;
char temp;
char_stack top;
top.s_top = NULL;
fgets(usr_in, sizeof(usr_in), stdin);
usr_in[strlen(usr_in)] = '';
temp = usr_in[strlen(usr_in) - 1];
char result[strlen(usr_in)] = {};;
if((temp == '+') || (temp == '-') || (temp == '*') || (temp == '/'))
{
strcpy(usr_in, rev_string(usr_in));
}
for(int i = 0; i < (sizeof(usr_in) - 1); i++)
{
push(&top, usr_in[i]);
}
return 0;
}
void push(char_stack *sPtr, char newChar)
{
char_node *newNode;
newNode = (char_node*)malloc(sizeof(char_node));
newNode->input = newChar;
newNode->next = sPtr->s_top;
sPtr->s_top = newNode;
return;
}
char pop(char_stack *sPtr)
{
char_node *tempPtr;
char tempChar;
tempPtr = sPtr->s_top;
tempChar = tempPtr->input;
sPtr->s_top = tempPtr->next;
free(tempPtr);
return tempChar;
}
char* rev_string(char *str)
{
int start, end, len;
char temp, *ptr = NULL;
len = strlen(str);
ptr = malloc(sizeof(char)*(len+1));
ptr = strcpy(ptr,str);
for (start=0,end=len-1; start<=end; start++,end--)
{
temp = ptr[start];
ptr[start] = ptr[end];
ptr[end] = temp;
}
return ptr;
}
Explanation / Answer
Hi, the following should help you.
Algorithm for Postfix to Infix can be as follows:
1.While there are input symbol left
2. Read the next symbol from input.
3. If the symbol is an operand
Push it onto the stack.
4. Otherwise,
the symbol is an operator.
5. If there are fewer than 2 values on the stack
Show Error /* input not sufficient values in the expression */
6. Else
Pop the top 2 values from the stack.
Put the operator, with the values as arguments and form a string.
Encapsulate the resulted string with parenthesis.
Push the resulted string back to stack.
7. If there is only one value in the stack
That value in the stack is the desired infix string.
8. If there are more values in the stack
Show Error /* The user input has too many values */
POSTFIX to INFIX implementation in C:
#include <stdio.h>
#include <stdlib.h>
int top = 10;
struct node
{
char ch;
struct node *next;
struct node *prev;
} *stack[11];
typedef struct node node;
void push(node *str)
{
if (top <= 0)
printf("Stack is Full ");
else
{
stack[top] = str;
top--;
}
}
node *pop()
{
node *exp;
if (top >= 10)
printf("Stack is Empty ");
else
exp = stack[++top];
return exp;
}
void convert(char exp[])
{
node *op1, *op2;
node *temp;
int i;
for (i=0;exp[i]!='';i++)
if (exp[i] >= 'a'&& exp[i] <= 'z'|| exp[i] >= 'A' && exp[i] <= 'Z')
{
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = NULL;
temp->prev = NULL;
push(temp);
}
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/' ||
exp[i] == '^')
{
op1 = pop();
op2 = pop();
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = op1;
temp->prev = op2;
push(temp);
}
}
void display(node *temp)
{
if (temp != NULL)
{
display(temp->prev);
printf("%c", temp->ch);
display(temp->next);
}
}
void main()
{
char exp[50];
clrscr();
printf("Enter the postfix expression :");
scanf("%s", exp);
convert(exp);
printf(" The Equivalant Infix expression is:");
display(pop());
printf(" ");
getch();
}
Algorithm for Prefix to Infix can be as follows:
CPP Program to convert prefix to Infix:
#include <iostream>
#include <stack>
using namespace std;
// function to check if character is operator or not
bool isOperator(char x) {
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
// Convert prefix to Infix expression
string preToInfix(string pre_exp) {
stack<string> s;
// length of expression
int length = pre_exp.size();
// reading from right to left
for (int i = length - 1; i >= 0; i--) {
// check if symbol is operator
if (isOperator(pre_exp[i])) {
// pop two operands from stack
string op1 = s.top(); s.pop();
string op2 = s.top(); s.pop();
// concat the operands and operator
string temp = "(" + op1 + pre_exp[i] + op2 + ")";
// Push string temp back to stack
s.push(temp);
}
// if symbol is an operand
else {
// push the operand to the stack
s.push(string(1, pre_exp[i]));
}
}
// Stack now contains the Infix expression
return s.top();
}
// Driver Code
int main() {
string pre_exp = "*-A/BC-/AKL";
cout << "Infix : " << preToInfix(pre_exp);
return 0;
}
Hope these two ways clear your queries.
#include <iostream>
#include <stack>
using namespace std;
// function to check if character is operator or not
bool isOperator(char x) {
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
// Convert prefix to Infix expression
string preToInfix(string pre_exp) {
stack<string> s;
// length of expression
int length = pre_exp.size();
// reading from right to left
for (int i = length - 1; i >= 0; i--) {
// check if symbol is operator
if (isOperator(pre_exp[i])) {
// pop two operands from stack
string op1 = s.top(); s.pop();
string op2 = s.top(); s.pop();
// concat the operands and operator
string temp = "(" + op1 + pre_exp[i] + op2 + ")";
// Push string temp back to stack
s.push(temp);
}
// if symbol is an operand
else {
// push the operand to the stack
s.push(string(1, pre_exp[i]));
}
}
// Stack now contains the Infix expression
return s.top();
}
// Driver Code
int main() {
string pre_exp = "*-A/BC-/AKL";
cout << "Infix : " << preToInfix(pre_exp);
return 0;
}
Hope these two ways clear your queries.