Question

In this project you will be writing a C++ program that uses a stack to convert an evaluate infix expression. Compilers often use this type of parsing. Note that the infix expression might not be syntactically correct.

Before evaluating an infix expression, you need to check if its balanced, then convert it to a postfix expression then finally evaluate the postfix.

You need to implement three methods:

1. public static Boolean checkBalance(String infixExpression)
2. public static String convertToPostfix(String infixExpression) 3. public static Double evaluatePostfix(String postFix)

Refer to your text book and class notes for the corresponding algorithms to implement these methods.

You need to use your own Stack implemented using Linked structure not C++ STL Stack. Your program should prompt the user for an expression, detect how many variables are there in the expression and prompt the user for their values.

Sample infix/Postfix Conversion

Infix Expression	Postfix Expression
a+b	a b+
a + b*c	a bc *+
a *b^ c	a bc ^ *
a + b*c ^ d	a bc d^ *+
( a + b ) *c	a b+ c *
(a +b ) * c	a b+ c *
( a + b ) / (c – d )	a b+ c d - /
( a + b * c^ d )^ ( e *f – g ^ h )	a b c d ^ * +e f * g h^ - ^
( a +b * c^ d ) ^( e* f– g h)	None. Invalid syntax. (What’s missing?)
a / b * c / d + ( e*f / g ^ h ) * (i – j)	a b / c * d / e f * g h^ / i j - * +

Sample input/output:

Enter your infix expression:
a+b*c
Your expression has 3 variables, please enter the value of variable 1: 3
please enter the value of variable 2:
6
please enter the value of variable 3:
28
Your equivalent postfix is:

abc*+
The evaluation is = 171.00

PLEASE ANSWER THE FOLLOWING IN C++!! I DON'T UNDERSTAND THE PROBLEM AT HANDS!! I WILL UPVOTE FOR WHOEVER ANSWERS IT CORRECTLY!! READ THE PROBLEM CAREFULLY!!!

Answer 1

PLEASE GIVE IT A THUMBS UP

#include<iostream>
#include <math.h>
#include <string.h>
#include<bits/stdc++.h>
#include<ctype.h> //for isdigit function
using namespace std;
int stackk[100];
int top=-1;
int value=0; //Global Declarations
int pop()
{

return (stackk[top--]);
}
void push(int x)
{
if(value==1)
{
int y;
y=pop();
stackk[++top]=x+10*y; //for more than one digit
}
else if(value==0)
{
stackk[++top]=x;
value=1;
}
}

void evaluate(char postfix[]){
char c;
int i=0,y,x;
while((c=postfix[i++])!='\0')
{
if(isdigit(c))
push(c-'0'); //for converting datatype
else if(c==',')
{
value=0;
}
else
{
x=pop(); //top element
y=pop(); //next top element
switch(c)
{
case'+':
push(x+y);
break;
case '-':
push(y-x);
break;
case '*':
push(y*x);
break;
case '/':
push(y/x);
break;
case '^':
push(pow(y,x));
break;
default:
cout<<"\nInvalid Operator";
}
}
}
cout<<"\n\nResult Of Evaluation:"<<stackk[top];
}

int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}

string infixToPostfix(string s)
{
std::stack<char> st;
st.push('N');
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))
ns+=s[i];
else if(s[i] == '(')
st.push('(');   
else if(s[i] == ')')
{
while(st.top() != 'N' && st.top() != '(')
{
char c = st.top();
st.pop();
ns += c;
}
if(st.top() == '(')
{
char c = st.top();
st.pop();
}
}   
else{
while(st.top() != 'N' && prec(s[i]) <= prec(st.top()))
{
char c = st.top();
st.pop();
ns += c;
}
st.push(s[i]);
}

}
while(st.top() != 'N')
{
char c = st.top();
st.pop();
ns += c;
}

return ns;

}

bool checkbalance(string s){
for(int i=0;i<s.length()-1;i++){
if((s[i]>='a' && s[i]<='z') && (s[i+1]>='a' && s[i+1]<='z'))
return false;
}
return true;
}

int main()
{
string exp;
cin>>exp;
if(checkbalance(exp)==0){
cout<<"Not balance"<<endl;
return 0;
}
else{
string s=infixToPostfix(exp);
int n = s.length();
int c_n=0;
for(int i=0;i<n;i++){
if(s[i]>='a' && s[i]<='z')
c_n++;
}
cout<<"Your expression has "<<c_n<<" variables"<<endl;
char c[100];
int c_i=0;
c_n=1;
for(int i=0;i<n;i++){
string v;
if(s[i]>='a' && s[i]<='z'){
cout<<"Enter the value of variable "<<c_n<<": ";
cin>>v;
for(int k=0;v[k]!='\0';k++){
c[c_i]=v[k];
c_i++;
}
c_n++;
}
else{
c[c_i]=(char)s[i];
c_i++;
}
c[c_i]=',';
c_i++;
}
c[c_i-1]='\0';
evaluate(c);
}
}