You will implement a calculator using stacks and queues in C++. You may use the
ID: 3872188 • Letter: Y
Question
You will implement a calculator using stacks and queues in C++. You may use the STL.
Your calculator must support the following operators:
• Addition: +
• Subtraction: –
• Multiplication: *
• Division: / • Modulo: %
• Exponent: ^
• Parentheses: ( and )
The input will be given in the form of infix expressions. For example, ( 20.4 + 3 ) * -5, where each operator or operand is separated by a space. Implement parentheses checking to ensure that the input is a valid expression. If the expression is not valid, output an error message. Convert the checked infix expression into a postfix expression. For example, the above infix expression would covert to 20.4 3 + -5 *. Use a stack for the infix to postfix conversion. Store the resulting postfix expression in a queue and print it onto the screen. Then, using a second stack, evaluate the postfix expression and print the result.
Here is sample output (input in bold green): Enter a valid infix expression: 3 + 4 * 5 / 6
The resulting postfix expression is: 3 4 5 * 6 / +
The result is: 6.33333
Your program should accept integers and floating-point numbers, including negative numbers, as operands. Additionally, your program should accept only those operators indicated above. You may assume valid infix expression input, though parentheses may be invalid (and need to be checked/matched). All operators, with the exception of exponent (^), have left-to-right associativity.
Submit your program source code and include a README file where you explain all the information required for the grader to grade your program (i.e., how to run it, an example, how you did it, etc.). Also submit a screen-shot of your program running. Be sure to include your name in each program and in the README file.
Explanation / Answer
// Chegg_05_InfixToPostfixUsingStack.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include<stdlib.h>
#include<string>
#include <stack>
#include <queue>
#include <iostream>
using namespace std;
//Function to return precedence of operators
int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
std::queue<char> infixToPostfix(string s)
{
std::stack<char> st;
std::queue<char> q;
st.push('N');
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
if(s[i] == ' ')
continue;
// If the scanned character is an operand, add it to output string.
if((s[i] >= '0' && s[i] <= '9'))
{
ns+=s[i];
q.push(s[i]);
}
// If the scanned character is an ‘(‘, push it to the stack.
else if(s[i] == '(')
st.push('(');
// If the scanned character is an ‘)’, pop and to output string from the stack
// until an ‘(‘ is encountered.
else if(s[i] == ')')
{
bool isPresent = false;
while(st.top() != 'N' && st.top() != '(')
{
char c = st.top();
st.pop();
ns += c;
q.push(c);
}
if(st.top() == '(')
{
char c = st.top();
st.pop();
isPresent = true;
}
if(!isPresent)
{
std::cout << "Infix expression is not a valid expression" << endl;
std::queue<char> empty;
std::swap( q, empty );
return q;
}
}
//If an operator is scanned
else{
while(st.top() != 'N' && prec(s[i]) <= prec(st.top()))
{
char c = st.top();
st.pop();
ns += c;
q.push(c);
}
st.push(s[i]);
}
}
//Pop all the remaining elements from the stack
while(st.top() != 'N')
{
char c = st.top();
if(c == '(')
{
std::cout << "Infix expression is not a valid expression" << endl;
std::queue<char> empty;
std::swap( q, empty );
return q;
}
st.pop();
ns += c;
q.push(c);
}
return q;
}
int eval(int op1, int op2, char operate) {
switch (operate) {
case '*': return op2 * op1;
case '/': return op2 / op1;
case '+': return op2 + op1;
case '-': return op2 - op1;
case '^':
{
int result =1;
for(int i = 0; i < op1; i++)
{
result*=op2;
}
return result;
}
default : return 0;
}
}
int evalPostfix(std::queue<char> q)
{
stack<int> s;
int i = 0;
char ch;
int val = 0;
int size = q.size();
while (i < size) {
ch = q.front();
q.pop();
if (isdigit(ch)) {
// we saw an operand
// push the digit onto stack
s.push(ch-'0');
}
else {
// we saw an operator
// pop off the top two operands from the
// stack and evalute them using the current
// operator
int op1 = s.top();
s.pop();
int op2 = s.top();
s.pop();
int temp = 2 ^ 3;
val = eval(op1, op2, ch);
// push the value obtained after evaluating
// onto the stack
s.push(val);
}
i++;
}
return val;
}
void PrintQueue(std::queue<char> q)
{
std::cout << "Postfix expression is: " ;
while (q.size()!=0)
{
std::cout<< q.front();
q.pop();
}
std::cout<< endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
string exp;
std::cout << "Intput the infix expression" << endl;
getline(cin,exp);
std::queue<char> q = infixToPostfix(exp);
if(q.size() > 0)
{
PrintQueue(q);
int result = evalPostfix(q);
std::cout << "Result is: " << result <<endl;
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.