Solving / Converting Expressions

Examples: Postfix Notations, Prefix Notions

caution

• Infix = (x*y) ... Operator[*] is between two operands[a,b]
• Prefix = (*xy) ... Operator[*] which was between two operands[a,b] now comes before the two operands
  • Postfix Notion / Reverse Polish notation / Polish Postfix Notation
• Postfix = (xy*) ... Operator[*] which was between two operands[a,b] now comes after the two operands

Solve braces (..) first and then use the result as operands and do postfix or prefix as required.

Infix to Postfix expression

info

• if str[i] is a digit i.e. isdigit(str[i]) [using isdigit() to check for a single digit character]
  • add digit meaning sr[i] to the resultingString

---

• if dq.empty()
  • add that operator to dq

---

• if str[i] == '('
  • add ( to the dq
  • then until reaching the `)`, keep adding those values to `dq` without comparing with their precedences like if we have `+` we will directly add `+` to dq without checking for precedence as `(` has the highest precedence

---

• if str[i] == ')'
  • keep popping and adding all elements from dq to resultingString until ( is found and also pop (

---

• if current str[i] has lower precedence than dq.back()

  • remove that higher precedence dq.back() and add that dq.back() to resultingString

  • add current low precedence str[i] to the dq

  • exmaple: if current str[i] is + or - and if (dq.back() == '*' || dq.back() == '/' || dq.back() == '+' || dq.back() == '-').

---

• if str[i] is * or dq.back() and (dq.back() == '/' || dq.back() == '*')
  • then remove the dq.back()[adding it to resultingString] as it will be coming first in given expression and thus will have higher precedence than later character[left to right .. higher to lower precedence]

string infix_to_postfix(string s)
{
    deque<char> dq;
    string resultingString = "";
    s.erase(remove(s.begin(), s.end(), ' '), s.end());
    for (int i = 0; i < s.size(); i++)
    {
        if (isdigit(s[i]))
        {
            resultingString.push_back(s[i]);
        }
        else if (dq.empty())
        {
            dq.emplace_back(s[i]);
        }
        else if (s[i] == '(')
        {
            dq.emplace_back(s[i]);
        }
        else if (s[i] == ')')
        {
            while (dq.back() != '(')
            {
                resultingString.push_back(dq.back());
                dq.pop_back();
            }
            dq.pop_back();
        }
        else if (s[i] == '+' || s[i] == '-')
        {
            if (dq.back() == '*' || dq.back() == '/' || dq.back() == '+' || dq.back() == '-')
            {
                resultingString.push_back(dq.back());
                dq.pop_back();
                dq.emplace_back(s[i]);
            }
            else
            {
                dq.emplace_back(s[i]);
            }
        }
        else if (s[i] == '*' || s[i] == '/')
        {
            if (dq.back() == '/' || dq.back() == '*')
            {
                resultingString.push_back(dq.back());
                dq.pop_back();
                dq.emplace_back(s[i]);
            }
            else
            {
                dq.emplace_back(s[i]);
            }
        }
    }

    while (!dq.empty())
    {
        resultingString.push_back(dq.back());
        dq.pop_back();
        ;
    }

    return resultingString; // the resulting string
}

Solving Postfix Expression

Solving Postfix Expression to get the Answer

info

• if v[i] is a number or alphabet such as 23, A, b, x, etc.

  • add that number or alphabet to dq

• if v[i] is operator like +, -, *, /, ^

  • get the last two dq.back() values and use the operator with them, like a+b, 6*7, etc.

int evalRPN(vector<string> &v)
{
    int result;
    deque<int> dq;
    int a, b;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] != "+" && v[i] != "-" && v[i] != "*" && v[i] != "/")
        {
            dq.emplace_back(stoi(v[i]));
        }
        else if (v[i] == "+")
        {
            b = dq.back();
            dq.pop_back();
            a = dq.back();
            dq.pop_back();
            dq.emplace_back(a + b);
        }
        else if (v[i] == "-")
        {
            b = dq.back();
            dq.pop_back();
            a = dq.back();
            dq.pop_back();
            dq.emplace_back(a - b);
        }
        else if (v[i] == "*")
        {
            b = dq.back();
            dq.pop_back();
            a = dq.back();
            dq.pop_back();
            dq.emplace_back(a * b);
        }
        else if (v[i] == "/")
        {
            b = dq.back();
            dq.pop_back();
            a = dq.back();
            dq.pop_back();
            dq.emplace_back(a / b);
        }
    }

    result = dq.back();
    return result;
}

only valid for +ve 1 digit numbers

/* Only for 1 digit +ve numbers */
int cal(string s) // taking a POSTFIX EXPRESSION as parameter
{
    deque<int> dq;
    int res = 0;
    int x;
    string ss;
    for (int i = 0; i < s.size(); i++)
    {
        if (isdigit(s[i]))
        {
            ss = s[i];
            x = stoi(ss);
            dq.emplace_back(x);
        }
        else if (s[i] == '+')
        {
            int b = dq.back(); // 2nd element
            dq.pop_back();
            int a = dq.back(); // 1st element
            dq.pop_back();
            dq.emplace_back(a + b);
        }
        else if (s[i] == '-')
        {
            int b = dq.back(); // 2nd element
            dq.pop_back();
            int a = dq.back(); // 1st element
            dq.pop_back();
            dq.emplace_back(a - b);
        }
        else if (s[i] == '*')
        {
            int b = dq.back(); // 2nd element
            dq.pop_back();
            int a = dq.back(); // 1st element
            dq.pop_back();
            dq.emplace_back(a * b);
        }
        else if (s[i] == '/')
        {
            int b = dq.back(); // 2nd element
            dq.pop_back();
            int a = dq.back(); // 1st element
            dq.pop_back();
            dq.emplace_back(a / b);
        }
    }
    if (dq.size() == s.size())
    {
        res = stoi(s);
    }
    else
    {
        res = dq.back();
    }
    return res;
}

---

Infix to Prefix expression

---

Solving Prefix expression

Postfix to Infix

---

Prefix to Infix

---