Answer:
See explaination
Explanation:
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
const int MAX = 100;
//stack structure
struct stack{
string st;
int top = -1;
//push an item to the stack
void push(char x)
{
if(top==MAX-1){
cout << "Stack overflow\n";
return;
}
st[++top] = x;
}
//delete the topmost element
char pop()
{
if(top==-1){
cout << "Stack underflow\n";
return 0;
}
return st[top--];
}
//return topmost element
char peek()
{
return st[top];
}
};
//function prototypes
int precedence(char x);
string convert(string infixExpression);
int evaluate(string postFix);
//main function
int main()
{
string infix, postfix;
do{
//prompt and read infix expression
cout<< "Enter expression (or exit to end):" <<endl;
getline(cin, infix);
if(infix=="exit") break;
if(infix[0]=='(' || isdigit(infix[0]))
{
cout << "Expression: " << infix << endl;
string postfix = convert(infix);
cout << "Postfix form: " << postfix <<endl;
int result = evaluate(postfix);
cout << "Result:" << result << endl;
}
else
cout << "Invalid expression" <<endl;
}while(1);
return 0;
}
//function to return precedence
int precedence(char x)
{
switch(x)
{
case '(':
return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default : return 999;
}
}
//function to convert from infix to postfix expression
string convert(string infix)
{
stack stk;
string postfix = "";
stk.push('(');
int count = 0;
for(int i=0; i<infix.size(); i++)
{
if(isalpha(infix[i]))
count++;
}
infix = infix + ")";
for(int i=0; i<infix.size(); i++)
{
char ch = infix[i];
if(ch==' ') continue;
if(isalpha(ch))
{
postfix = postfix + " " + ch;
}
else if(ch=='(')
{
stk.push('(');
}
else if(ch==')')
{
while(stk.peek()!='(')
{
postfix = postfix + " " + stk.pop();
}
stk.pop();
}
else
{
int p1 = precedence(ch);
int p2 = precedence(stk.peek());
while(p1<=p2)
{
postfix = postfix + " " + stk.pop();
p2=precedence(stk.peek());
}
stk.push(ch);
}
}
return postfix;
}
//function to evaluate postfix expression
int evaluate(string postFix)
{
stack stk;
for(int i=0; i<postFix.size(); i++)
{
char c = postFix[i];
if(c==' ') continue;
if(isdigit(c))
{
int val = c - '0';
stk.push(val);
}
else
{
int x = stk.pop();
int y = stk.pop();
switch(c)
{
case '+':
stk.push(y+x);
break;
case '-':
stk.push(y-x);
break;
case '*':
stk.push(y*x);
break;
case '/':
stk.push(y/x);
break;
case '^':
stk.push(pow(y,x));
break;
}
}
}
return stk.pop();
}
