code in c++ Arithmetic Notation, Shunting Yard Algorithm In this lab you will pa

Question

code in c++

Arithmetic Notation, Shunting Yard Algorithm In this lab you will parse an infix notation algebraic expression, which may have parentheses, inputted from a file Use a stack shunting yard algorithm and STL stack to create a postfix expression string Introduction Important programming concepts for this lab are Arithmetic Algebraic Expressions, the different expression notations like Prefix, Postfx and Infix, the evaluation order of the expressions (precedence), and how to convert an expression from one notation to another. Each concept is backed by algorithms, and Pre-Visualizations illustrative examples to understand concepts clearly. We will be using the concepts of Stacks using a shunting yard algorithm to build a postfix expression string Arithmetic Algebraic Expressions and Notation In algebraic expression is a made up of a legal combination of operands and operators. Tokens are the symbols that make up an expression Tokens can be operands or operators Operators operate on operands, binary operators operate on two operands. Binary operators are tokens that signify a mathematical operation between the two operands The operands represent the quantity (unit of data) on which an arithmetical operation is performed. For our purpose for this lab, the algebraic expressions are restricted to the following: Each token is a character e For example A is represented as the character 'A . There are no blanks (spaces) allowed in the expression string to be parsed .Operand tokens can be sing le letter unsigned variables alphabet characters (x y,z, A, B, C) .All expressions are binary .All operators are the binary operators:t, , *,/ .Parentheses, the[ ( and [) ] characters, are valid expression tokens that will guide formation of the postfix expression The input infix String expression is assumed to be follow the rules and does not require rules checking of the input expressions Considering the aforementioned definitions for a binary expression, we can write an example of an infix expression as Algebraic Expressions can be represented us ing three different common notations. INFIX Expressions in which operands surround the operator, e.g. xty, 6*3 etc. This way of writing the Expressions is called infix notation. It may require use of parentheses to dictate the evaluation order PREFIX: Prefix notation, also known as Polish notation, is a prefix notation, the operator comes before the operands, e.g. +xy, *+xyz etc. symbolic logic invented by Polish mathematician Jan Lukasiewicz in the 1920s, In the POSTFIX: Postfix notation is also known as Reverse Polish notation. In this notation, the postfix notation, the operator comes after the operands, e-g·xy+, xyzt z+ etc

Explanation / Answer

C++ CODE :

#include <fstream>
#include <iostream>
#include<bits/stdc++.h>
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;
}

//main function which returns us the postfix string

string infixToPostfix(string s)
{
    std::stack<char> st;
    st.push('N');
    int l = s.length();
    string ns;
    for(int i = 0; i < l; i++)
    {
        // If the scanned character is an operand, add it to output string.
        if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))
        ns+=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] == ')')
        {
            while(st.top() != 'N' && st.top() != '(')
            {
                char c = st.top();
                st.pop();
               ns += c;
            }
            if(st.top() == '(')
            {
                char c = st.top();
                st.pop();
            }
        }
       
        //If an operator is scanned
        else{
            while(st.top() != 'N' && prec(s[i]) <= prec(st.top()))
            {
                char c = st.top();
                st.pop();
                ns += c;
            }
            st.push(s[i]);
        }

    }
    //Pop all the remaining elements from the stack
    while(st.top() != 'N')
    {
        char c = st.top();
        st.pop();
        ns += c;
    }
   
    return ns;

}

int main(){
   string x;
   ifstream inFile;
   inFile.open("result.txt");
   while(inFile >> x){
       cout<<"INPUT INFIX STRING "<<x<<endl; //print input string here
       cout<<"OUTPUT POSTFIX STRING "<<infixToPostfix(x)<<endl; //pass input string to infixToPostfix function to get result
   }
   inFile.close();
}

SAMPLE TESTCASES :-

input file(result.txt)

(A+(B*C))
((A+B)*(Z+X))
((A+T)*((B+(A+C))^(C+D)))

output:

INPUT INFIX STRING (A+(B*C))
OUTPUT POSTFIX STRING ABC*+
INPUT INFIX STRING ((A+B)*(Z+X))
OUTPUT POSTFIX STRING AB+ZX+*
INPUT INFIX STRING ((A+T)*((B+(A+C))^(C+D)))
OUTPUT POSTFIX STRING AT+BAC++CD+^*

In case you find the answer useful, please give thums up(really helpful).

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.