Question

I need assistance with this code. Is there any way I can create this stack class (dealing with infix to postfix then postfix evaluation) without utilizing <stdio.h> and <math.h>?

____________________________________________________________________________________________

C++ Program:

#include <iostream>
#include <string>
#include <stdio.h>
#include <math.h>

using namespace std;

//Stack class
class STACK
{
private:
char *str;
int N;

public:
//Constructor
STACK(int maxN)
{
str = new char[maxN];
N = -1;
}

//Function that checks for empty
int empty()
{
return (N == -1);
}

//Push operation
void push(char val)
{
N = N + 1;
str[N] = val;
}

//Pop Operation
char pop()
{
char val;
val = str[N];
N = N-1;
return val;
}

char top()
{
return str[N];
}
};

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

//Function that converts infix to postfix
char* InfixToPostfix(string expr, int len)
{
int i, j;

char *postfix;

//Stack object
STACK postfixStack(len);

//Allocating memory
postfix = (char*)malloc(sizeof(char)*len);

//Set j to 0
j = 0;

//Iterating over string
for (i = 0; i < len; i++)
{
//If closing braces is encountered
if (expr[i] == ')')
{
//Popping element
postfix[j] = postfixStack.pop();
j++;
}

//If operator
else if ((expr[i] == '+') || (expr[i] == '*') || (expr[i] == '^') || (expr[i] == '-') || (expr[i] == '/'))
{
if((preced(expr[i]) > preced(postfixStack.top())))
{
postfixStack.push(expr[i]);
}
else
{
while( (!postfixStack.empty()) && (preced(expr[i]) <= preced(postfixStack.top())) )
{
//Placing operand on postfix expression string
postfix[j] = postfixStack.pop();
j++;
}
postfixStack.push(expr[i]);
}
}

//If Operand
else if ((expr[i] >= '0') && (expr[i] <= '9'))
{
//Placing operand on postfix expression string
postfix[j] = expr[i];
j++;
}
}

//Popping all elements from stack
while(!postfixStack.empty())
{
//Writing to postfix expression
postfix[j] = postfixStack.pop();
j++;
}

//Set string termination character
postfix[j]='\0';

return postfix;
}

//Function that evaluates postfix expression
double evaluatePostFix(char* postfix)
{
//Finding length
int len = strlen(postfix);
int a, b;

//Stack to evaluate postfix expression
STACK postfixStack(len);

//Iterating over expression
for (int i = 0; i < len; i++)
{
//If operator
if (postfix[i] == '+' || postfix[i] == '^' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/')
{
//Popping two operands
a = (postfixStack.pop()) - '0';
b = (postfixStack.pop()) - '0';

//Calculating corresponding operation
switch(postfix[i])
{
case '+': postfixStack.push((a+b) + '0'); break;
case '-': postfixStack.push((a-b) + '0'); break;
case '*': postfixStack.push((a*b) + '0'); break;
case '/': postfixStack.push((a/b) + '0'); break;
case '^': postfixStack.push((pow(double(a), double(b))) + '0'); break;
}
}

//If operand
else if ((postfix[i] >= '0') && (postfix[i] <= '9'))
{
//Storing operand into stack
postfixStack.push(postfix[i]);
}
}

//Returning result
return (postfixStack.pop()) - '0';
}

//Main function
int main()
{
double result;
int len;
string expr;
char* postfix;

//Reading expression
cout<<"\n Input Infix expression: ";
getline(cin, expr);

//Finding length
len = strlen(expr.c_str());

//Allocating memory
postfix = (char*)malloc(sizeof(char)*len);

//Converting Infix to Postfix expression
postfix = InfixToPostfix(expr, len);

//Printing postfix expression
cout<< "\n Postfix Expression: " << postfix << " \n";

//Evaluating postfix expression
result = evaluatePostFix(postfix);

cout << "\n Result: " << result << " \n\n";

return 0;
}

____________________________________________________________________________________________

Sample Run:

CTClinfixPostfix)bin\DebuginfixPostfix.exe Input Infix expression: 5*2+3 Postfix Expression: 52*3+ Result: 13 Process returned (0x execution time 2.894 s Press any key to continue.

Answer 1

C++ Code to Convert Infix expression to Postfix expression using Stack and Evaluate Postfix expression

CODE:

#include<iostream>
#include<stack>
#include<string>
#include<cmath>

using namespace std;

// Function to convert Infix expression to postfix
string InfixToPostfix(string expression);

// Function to verify whether an operator has higher precedence over other
Int has higher precedence(char operator1, char operator2);

// Function to verify whether a character is an 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);

float scanNum(char ch) {
int value;
value = ch;
return float(value-'0'); //return float from character
}
int isOperator(char ch) {
if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
return 1; //character is an operator
return -1; //not an operator
}
int isOperand(char ch) {
if(ch >= '0' && ch <= '9')
return 1; //character is an operand
return -1; //not an operand
}
float operation(int a, int b, char op) {
//Perform operation
if(op == '+')
return b+a;
else if(op == '-')
return b-a;
else if(op == '*')
return b*a;
else if(op == '/')
return b/a;
else if(op == '^')
return pow(b,a); //find b^a
else
return 0; //return negative infinity
}
float postfixEval(string postfix) {
int a, b;
stack<float> stk; // Declaring a Stack
string::iterator it;
for(it=postfix.begin(); it!=postfix.end(); it++) {
//read elements and perform postfix evaluation
if(isOperator(*it) != -1) {
a = stk.top();
stk.pop();
b = stk.top();
stk.pop();
stk.push(operation(a, b, *it));
}else if(isOperand(*it) > 0) {
stk.push(scanNum(*it));
}
}
return stk.top();
}

int main()
{
string expression;
cout<<"\nEnter Infix Expression: ";
getline(cin,expression);
cout<<"\n";
string postfix = InfixToPostfix(expression);
cout<<"PostFixExpression = "<<postfix <<" \n";
cout<<"\n";
cout << "The result is: "<<postfixEval(postfix);
}

// Function to evaluate Postfix expression and return output
string InfixToPostfix(string expression)
{
// Declaring a Stack from Standard template library in C++.
stack<char> S;
string postfix = ""; // Initialize postfix as empty string.
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(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();
}
}

while(!S.empty()) {
postfix += S.top();
S.pop();
}

return postfix;
}

// Function to verify whether a character is an english letter or a numeric digit.
// We are assuming in this solution that operand will be a single character
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 an 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;
}

// Function to get a weight of an operator. An operator with a higher weight will have higher precedence.
int GetOperatorWeight(char op)
{
int weight = -1;
switch(op)
{
case '+':
case '-':
weight = 1;
case '*':
case '/':
weight = 2;
case '$':
weight = 3;
}
return weight;
}

// Function to perform an operation and return output.
int HasHigherPrecedence(char op1, char op2)
{
int op1Weight = GetOperatorWeight(op1);
int op2Weight = GetOperatorWeight(op2);

// If operators have equal precedence, return true if they are left associative.
// return false, if right associative.
// if operator is left-associative, left one should be given priority.
if(op1Weight == op2Weight)
{
if(IsRightAssociative(op1)) return false;
else return true;
}
return op1Weight > op2Weight ? true: false;
}

Output:

Enter Infix Expression: 5*2+3 PostFixExpression52+3+ The result is: 13

Please give Thumbsup...