Adding on to the program below, allow the program to read a postfix expression c
ID: 3903154 • Letter: A
Question
Adding on to the program below, allow the program to read a postfix expression consisting of single digits and operators into a character array. Using the stack functions implemented earlier in the program below, the program should scan the expression and evaluate it.
#include<iostream>
#include<stack>
#include<string>
using namespace std;
string InfixToPostfix(string expression);
int HasHigherPrecedence(char operator1, char operator2);
// Function to verify whether a character is a operator symbol or not.
bool IsOperator(char C);
// Function to verify whether a character is alphanumeric chanaracter (letter or numeric digit) or not.
bool IsOperand(char C);
int main(int argc, char* argv[])
{
system("cls");
string expression;
cout << "Enter Infix Expression ";
getline(cin, expression);
string postfix = InfixToPostfix(expression);
cout << "Output = " << postfix << " ";
system("PAUSE");
return 0;
}
// Function to evaluate postfix expression and return output
string InfixToPostfix(string expression)
{
// Declaring a stack
stack<char> S;
string postfix = ""; // Initializing postfix as empty string.
for (int i = 0; i< expression.length(); i++)
{
if (expression[i] == ' ' || expression[i] == ',') continue;
// If character is operator, pop two elements from stack, perform operation and push the result back.
else if (IsOperator(expression[i]))
{
while (!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(), expression[i]))
{
postfix += S.top();
S.pop();
}
S.push(expression[i]);
}
// Else if character is an operand
else if (IsOperand(expression[i]))
{
postfix += expression[i];
}
else if (expression[i] == '(')
{
S.push(expression[i]);
}
else if (expression[i] == ')')
{
while (!S.empty() && S.top() != '(') {
postfix += S.top();
S.pop();
}
S.pop();
}
else {
printf("Invalid expression. ");
exit(1);
}
}
while (!S.empty()) {
postfix += S.top();
S.pop();
}
return postfix;
}
bool IsOperand(char C)
{
if (C >= '0' && C <= '9') return true;
if (C >= 'a' && C <= 'z') return true;
if (C >= 'A' && C <= 'Z') return true;
return false;
}
// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C)
{
if (C == '+' || C == '-' || C == '*' || C == '/' || C == '$')
return true;
return false;
}
// Function to verify whether an operator is right associative or not.
int IsRightAssociative(char op)
{
if (op == '$') return true;
return false;
}
int GetOperatorWeight(char op)
{
int weight = -1;
switch (op)
{
case '+':
case '-':
weight = 1;
case '*':
case '/':
weight = 2;
case '$':
weight = 3;
}
return weight;
}
int HasHigherPrecedence(char op1, char op2)
{
int op1Weight = GetOperatorWeight(op1);
int op2Weight = GetOperatorWeight(op2);
if (op1Weight == op2Weight)
{
if (IsRightAssociative(op1)) return false;
else return true;
}
return op1Weight > op2Weight ? true : false;
}
Explanation / Answer
Main Function modification
int main(int argc, char* argv[])
{
system("cls");
string expression;
cout << "1.Enter Infix Expression ";
cout << "2.Enter Postfix Expression ";
int n;
cout << "Enter choice:";
cin >> n;
if (n == 1){
getline(cin, expression);
string postfix = InfixToPostfix(expression);
cout << "Output = " << postfix << " ";
int k = evaluatePostfix(postfix);
cout << "Result: " << evaluatePostfix(postfix) << endl;
system("PAUSE");
if (n == 2){
getline(cin, expression);
cout << "Result: " << evaluatePostfix(postfix) << endl;
system("PAUSE");
return 0;
}
Postfix Evaluator
int evaluatePostfix(char* exp)
{
stack<char> S;
int i;
for (i = 0; exp[i]; ++i)
{
if (isdigit(exp[i]))
S.push(exp[i]);
else
{
int val1 = S.top;
S.pop();
int val2 = S.top;
S.pop();
switch (exp[i])
{
case '+': S.push(val2 + val1); break;
case '-': S.push(val2 - val1); break;
case '*': S.push(val2 * val1); break;
case '/': S.push(val2/val1); break;
}
}
}
return S.top;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.