Infix A+B A+B-C A*B-C A+B*C (A+B)*C Postfix: AB+ AB+C AB*C ABC*+ AB+C* AB+CD-/ A
ID: 3740412 • Letter: I
Question
Infix A+B A+B-C A*B-C A+B*C (A+B)*C Postfix: AB+ AB+C AB*C ABC*+ AB+C* AB+CD-/ ABC/+D AB*CDE/-+ A+B/C-D A*B+(C-D/E) A*B+C/D-E A B+CI(D-E) A (B+C/(D-E) AB*CDE-/+ ABCDE-/+* An infix expression can be defined as: | expression> | ( ) operator>- +|-1*|/ Each operand is one character long. Operators * and I have the same precedence while and-have the same precedence. However, and?have higher precedence than + and Order of precedence can be changed by enclosing the operands by a pair of parenthesis. Spaces between operand and operator are optional You should check whether the input string is a correct representation of an expression according to the above definition of , especially the balancing of pairs of parenthesis ( and)Explanation / Answer
/*
Evaluation Of postfix Expression in C++
Input Postfix expression must be in a desired format.
Operands must be integers and there should be space in between two operands.
Only '+' , '-' , '*' and '/' operators are expected.
*/
#include<iostream>
#include<stack>
#include<string>
using namespace std;
// Function to evaluate Postfix expression and return output
int EvalPostfix(string expression);
// Function to perform an operation and return output.
int PerformOp(char operation, int operand1, int operand2);
// Function to verify whether a character is operator symbol or not.
bool IsOp(char C);
// Function to verify whether a character is numeric digit.
bool IsNum(char C);
int main()
{
string expression;
cout<<"Enter Postfix Expression ";
getline(cin,expression);
int result = EvalPostfix(expression);
cout<<"Output = "<<result<<" ";
}
// Function to evaluate Postfix expression and return output
int EvalPostfix(string expression)
{
// Declaring a Stack from Standard template library in C++.
stack<int> S;
for(int i = 0;i< expression.length();i++) {
// Scanning each character from left.
// If character is a delimitter, move on.
if(expression[i] == ' ' || expression[i] == ',') continue;
// If character is operator, pop two elements from stack, perform operation and push the result back.
else if(IsOp(expression[i])) {
// Pop two operands.
int operand2 = S.top(); S.pop();
int operand1 = S.top(); S.pop();
// Perform operation
int result = PerformOp(expression[i], operand1, operand2);
//Push back result of operation on stack.
S.push(result);
}
else if(IsNum(expression[i])){
// Extract the numeric operand from the string
// Keep incrementing i as long as you are getting a numeric digit.
int operand = 0;
while(i<expression.length() && IsNum(expression[i])) {
// For a number with more than one digits, as we are scanning from left to right.
// Everytime , we get a digit towards right, we can multiply current total in operand by 10
// and add the new digit.
operand = (operand*10) + (expression[i] - '0');
i++;
}
// Finally, you will come out of while loop with i set to a non-numeric character or end of string
// decrement i because it will be incremented in increment section of loop once again.
// We do not want to skip the non-numeric character by incrementing i twice.
i--;
// Push operand on stack.
S.push(operand);
}
}
// If expression is in correct format, Stack will finally have one element. This will be the output.
return S.top();
}
// Function to verify whether a character is numeric digit.
bool IsNum(char C)
{
if(C >= '0' && C <= '9') return true;
return false;
}
// Function to verify whether a character is operator symbol or not.
bool IsOp(char C)
{
if(C == '+' || C == '-' || C == '*' || C == '/')
return true;
return false;
}
// Function to perform an operation and return output.
int PerformOp(char operation, int operand1, int operand2)
{
if(operation == '+') return operand1 +operand2;
else if(operation == '-') return operand1 - operand2;
else if(operation == '*') return operand1 * operand2;
else if(operation == '/') return operand1 / operand2;
else cout<<"Unexpected Error ";
return -1;
}