{"id":81401,"date":"2021-07-01T09:00:53","date_gmt":"2021-07-01T03:30:53","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=81401"},"modified":"2021-07-01T09:00:53","modified_gmt":"2021-07-01T03:30:53","slug":"expression-parsing-in-data-structure","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/","title":{"rendered":"Expression Parsing in Data Structure"},"content":{"rendered":"

An expression is a statement that generates a value on evaluation. Parsing means analyzing a string or a set of symbols one by one depending on a particular criterion. Expression parsing a term used in a programming language to evaluate arithmetic and logical expressions.<\/p>\n

Whenever we input an expression into the computer, it reads it as a string and parses it to generate the relevant output. An expression looks something as follows: a+b^c-d+x*p.<\/p>\n

Expression Parsing in Data Structure<\/h3>\n

In data structures, expression parsing is used to evaluate logical and arithmetic expressions. We can describe arithmetic operations in the form of a notation. There are three ways to write an arithmetic expression i.e. three different notations for arithmetic expressions:<\/p>\n

1. Infix notation
\n2. Postfix notation
\n3. Prefix notation<\/p>\n

We need to note here that a notation is just a form of representation. The output of the expression remains the same irrespective of the notation used.<\/p>\n

Before digging deeper into these notations, let us first understand the concept of precedence and associativity.<\/p>\n

Associativity in Expression Parsing<\/h3>\n

Associativity comes into the picture when an expression contains an operator more than once. It is also used whenever an expression has two or more operators of the same precedence.<\/p>\n

In such cases, we need to decide the priority\/order of evaluation of every operator. Associativity can be either:<\/p>\n

1. Left to righ<\/strong>t or
\n2. Right to left<\/strong><\/p>\n

Example of Expression Parsing<\/strong><\/p>\n

Consider the expression p+q-r.<\/p>\n

Here, both + and – have the same precedence, so which of the two will evaluate first? This decision will be made by associativity. Both + and – have left to right associativity. Thus, the addition will evaluate before subtraction.<\/p>\n

Let an expression be 5+10-4. We will evaluate (5 + 10) first which is equal to 15. Then we will perform subtraction i.e. 15 – 4 = 11.<\/p>\n

Thus, the outcome of the expression will be 11.<\/p>\n

Example 2:<\/strong>
\nConsider the expression p*q\/r. Both * and \/ have the same precedence but the associativity is left to right.
\nHence multiplication will occur first.<\/p>\n

Let an expression be 20*5\/10. Firstly, 20*5 will evaluate which gives out 100. Then division will evaluate i.e. 100\/10 = 10.<\/p>\n

Thus, 10 will be the outcome.<\/p>\n

Precedence in Expression Parsing<\/h3>\n

Precedence defines the order which the operators must follow during the evaluation of an expression. The order of operators is always decided by the precedence first.<\/p>\n

If precedence fails to decide the order, we take the help of associativity to do so. This mostly occurs when an expression contains two or more operators of the same precedence.<\/p>\n

The following table shows the decreasing order of precedence of operators along with their associativity.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
S. No.<\/strong><\/td>\nOperator<\/strong><\/td>\nDescription\u00a0<\/strong><\/td>\nAssociativity\u00a0<\/strong><\/td>\n<\/tr>\n
1<\/span><\/td>\n( )<\/span><\/td>\nParentheses\u00a0<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
2<\/span><\/td>\n[ ]<\/span><\/td>\nBrackets\u00a0<\/span><\/td>\n<\/tr>\n
3<\/span><\/td>\n.<\/span><\/td>\nObject\u00a0<\/span><\/td>\n<\/tr>\n
4<\/span><\/td>\n-><\/span><\/td>\nPointer\u00a0<\/span><\/td>\n<\/tr>\n
5<\/span><\/td>\n++ \u00a0 —<\/span><\/td>\nPostfix increment and decrement<\/span><\/td>\n<\/tr>\n
6<\/span><\/td>\n++\u00a0 —<\/span><\/td>\nPrefix increment and decrement<\/span><\/td>\nRight to left<\/span><\/td>\n<\/tr>\n
7<\/span><\/td>\n\n
    \n
  • –<\/span><\/li>\n<\/ul>\n<\/td>\n
Unary plus\/minus<\/span><\/td>\n<\/tr>\n
8<\/span><\/td>\n!~<\/span><\/td>\nLogical negation and bitwise complement<\/span><\/td>\n<\/tr>\n
9<\/span><\/td>\n(type)<\/span><\/td>\nCast\u00a0<\/span><\/td>\n<\/tr>\n
10<\/span><\/td>\n*<\/span><\/td>\nDereference operator<\/span><\/td>\n<\/tr>\n
11<\/span><\/td>\n&<\/span><\/td>\nAddress of operator<\/span><\/td>\n<\/tr>\n
12<\/span><\/td>\nsizeof<\/span><\/td>\nUnary operator, returns size in bytes.<\/span><\/td>\n<\/tr>\n
13<\/span><\/td>\n* \/ %<\/span><\/td>\nMultiplication\/ division\/ modulus\u00a0<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
14<\/span><\/td>\n\n
    \n
  • –<\/span><\/li>\n<\/ul>\n<\/td>\n
Addition\/ Subtraction<\/span><\/td>\n<\/tr>\n
15<\/span><\/td>\n<<\u00a0 >><\/span><\/td>\nBitwise left shift\/ Bitwise right shift<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
16<\/span><\/td>\n<\u00a0 <=<\/span><\/td>\nRelation less than, less than or equal to<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
17<\/span><\/td>\n>\u00a0 >=<\/span><\/td>\nRelational greater than, greater than or equal to<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
18<\/span><\/td>\n==\u00a0 !=<\/span><\/td>\nIs equal to, Not equal to<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
19<\/span><\/td>\n&<\/span><\/td>\nBitwise AND<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
20<\/span><\/td>\n^<\/span><\/td>\nBitwise exclusive OR<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
21<\/span><\/td>\n|<\/span><\/td>\nBitwise inclusive OR<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
22<\/span><\/td>\n&&<\/span><\/td>\nLogical AND<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
23<\/span><\/td>\n||<\/span><\/td>\nLogical OR<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
24<\/span><\/td>\n? :<\/span><\/td>\nTernary operator<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n
25<\/span><\/td>\n=<\/span><\/td>\nAssignment operator<\/span><\/td>\nRight to left<\/span><\/td>\n<\/tr>\n
26<\/span><\/td>\n+=\u00a0 -=<\/span><\/td>\nAddition\/Subtraction assignment<\/span><\/td>\n<\/tr>\n
27<\/span><\/td>\n*=\u00a0 \/=<\/span><\/td>\nMultiplication\/division assignment<\/span><\/td>\n<\/tr>\n
28<\/span><\/td>\n%=\u00a0 &=<\/span><\/td>\nModulus\/Bitwise AND assignment\u00a0<\/span><\/td>\n<\/tr>\n
29<\/span><\/td>\n^=\u00a0 |=<\/span><\/td>\nBitwise exclusive\/ Bitwise inclusive OR<\/span><\/td>\n<\/tr>\n
30<\/span><\/td>\n<<=\u00a0 >>=<\/span><\/td>\nBitwise left shift\/ Bitwise right shift assignment<\/span><\/td>\n<\/tr>\n
31<\/span><\/td>\n,<\/span><\/td>\nComma operator<\/span><\/td>\nLeft to right<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Types of Notations:<\/h3>\n

As discussed above, there are three types of notations:<\/p>\n

1. Infix
\n2. Postfix
\n3. Prefix<\/p>\n

Let us discuss them in detail.<\/p>\n

1. Infix Notation<\/h4>\n

In this notation, the operator is in-between both the operands. It is the easiest readable form of expression for humans. However, it is very complex for the computer. This is why whenever we input an infix expression into the program, the compiler first converts it into postfix notation and then evaluates it.<\/p>\n

For a computer, infix notation requires a lot of memory and time for computation. The following expression represents an infix notation: (p+q) * (r-s)<\/p>\n

2. Postfix notation<\/h4>\n

It is also known as reverse polish notation. In postfix notation, the operators are written after the operand. The following expression represents a postfix notation: pq+rs-*<\/p>\n

3. Prefix Notation<\/h4>\n

It is also known as polish notation. In this notation, the operator comes before the operands. The following expression represents the prefix notation: *+pq-rs<\/p>\n

Expression Parsing in Data Structure<\/h3>\n

To parse any expression, the first thing we need is to take into consideration associativity and the order of precedence.<\/p>\n

But why do we need to parse an expression? The answer is simple. The algorithms that are designed in infix are not very efficient. Therefore, we need to convert the infix expressions into a prefix or postfix expression.<\/p>\n

Let us check two different conversions:
\n1. Infix to postfix
\n2. Infix to prefix<\/p>\n

1. Infix to Prefix Conversion:<\/h4>\n

We can convert an infix expression into a prefix or postfix expression without or with using stack.<\/p>\n

Let us first see an infix conversion into prefix without the help of a stack.<\/p>\n

Consider an expression: A+((B*C-D\/E)^F^G)+H<\/p>\n

Step 1:<\/strong> First, we will solve B*C i.e. A + ((*BC<\/strong> – D\/E) ^F ^ G) + H
\nStep 2:<\/strong> A + ((*BC – \/DE<\/strong>) ^F ^ G) + H
\nStep 3:<\/strong> A + (( -*BC \/DE<\/strong>) ^F ^ G) + H
\nStep 4:<\/strong> A + (( -*BC \/DE) ^ ^FG<\/strong>) + H
\nStep 5<\/strong>: A + (^ -*BC \/DE ^FG<\/strong>) + H
\nStep 6:<\/strong> + A (^ -*BC \/DE ^FG)<\/strong> + H
\nStep 7: + + A (^ -*BC \/DE ^FG) H<\/strong><\/p>\n

Thus, according to the order of precedence and associativity, we have calculated the prefix expression from the infix expression.<\/p>\n

Infix to Prefix Conversion Using Stack<\/h5>\n

Consider the expression: A+(B-C)*D-E\/F<\/p>\n

Step 1:<\/strong> Reverse the expression as shown: F\/E-D*)C-B(+A
\nStep 2:<\/strong><\/p>\n\n\n\n\n\n\n\n\n\n\n\n
Input symbol<\/b><\/td>\nStack\u00a0<\/b><\/td>\nPrefix\u00a0<\/b><\/td>\n<\/tr>\n
F<\/span><\/td>\nEmpty\u00a0<\/span><\/td>\nF<\/span><\/td>\n<\/tr>\n
\/<\/span><\/td>\n\/<\/span><\/td>\nF<\/span><\/td>\n<\/tr>\n
E<\/span><\/td>\n\/<\/span><\/td>\nFE<\/span><\/td>\n<\/tr>\n
–<\/span><\/td>\n–<\/span><\/td>\nFE\/<\/span><\/td>\n<\/tr>\n
D<\/span><\/td>\n–<\/span><\/td>\nFE\/D<\/span><\/td>\n<\/tr>\n
*<\/span><\/td>\n-*<\/span><\/td>\nFE\/D<\/span><\/td>\n<\/tr>\n
)<\/span><\/td>\n-*)<\/span><\/td>\nFE\/D<\/span><\/td>\n<\/tr>\n
C<\/span><\/td>\n-*)<\/span><\/td>\nFE\/DC<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Step 3<\/strong>: Reverse the results -+A*-BCD\/EF<\/strong><\/p>\n

Infix to Postfix Conversion:<\/h4>\n

We can convert the infix expression to postfix expression with or without using stack. Let us see the conversion with the help of the stack.<\/p>\n

Consider the following expression:
\nA+(B*C\/D-E^F^I+G)\/H<\/strong><\/p>\n

Its postfix will be:<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Input symbol<\/b><\/td>\nStack\u00a0<\/b><\/td>\nPostfix\u00a0<\/b><\/td>\n<\/tr>\n
A<\/span><\/td>\nEmpty\u00a0<\/span><\/td>\nA<\/span><\/td>\n<\/tr>\n
+<\/span><\/td>\n+<\/span><\/td>\nA<\/span><\/td>\n<\/tr>\n
(<\/span><\/td>\n+(<\/span><\/td>\nA<\/span><\/td>\n<\/tr>\n
B<\/span><\/td>\n+(<\/span><\/td>\nAB<\/span><\/td>\n<\/tr>\n
*<\/span><\/td>\n+(*<\/span><\/td>\nAB<\/span><\/td>\n<\/tr>\n
C<\/span><\/td>\n+(*<\/span><\/td>\nABC<\/span><\/td>\n<\/tr>\n
\/<\/span><\/td>\n+(\/<\/span><\/td>\nABC*<\/span><\/td>\n<\/tr>\n
D<\/span><\/td>\n+(\/<\/span><\/td>\nABC*D<\/span><\/td>\n<\/tr>\n
–<\/span><\/td>\n+(-<\/span><\/td>\nABC*D\/<\/span><\/td>\n<\/tr>\n
E<\/span><\/td>\n+(-<\/span><\/td>\nABC*D\/E<\/span><\/td>\n<\/tr>\n
^<\/span><\/td>\n+(-^<\/span><\/td>\nABC*D\/E<\/span><\/td>\n<\/tr>\n
F<\/span><\/td>\n+(-^<\/span><\/td>\nABC*D\/EF<\/span><\/td>\n<\/tr>\n
^<\/span><\/td>\n+(-^^<\/span><\/td>\nABC*D\/EF<\/span><\/td>\n<\/tr>\n
I<\/span><\/td>\n+(-^^<\/span><\/td>\nABC*D\/EFI<\/span><\/td>\n<\/tr>\n
+<\/span><\/td>\n+(+<\/span><\/td>\nABC*D\/EFI^^-<\/span><\/td>\n<\/tr>\n
G<\/span><\/td>\n+(+<\/span><\/td>\nABC*D\/EFI^^-G<\/span><\/td>\n<\/tr>\n
)<\/span><\/td>\n+<\/span><\/td>\nABC*D\/EFI^^-G+<\/span><\/td>\n<\/tr>\n
\/<\/span><\/td>\n+\/<\/span><\/td>\nABC*D\/EFI^^-G+<\/span><\/td>\n<\/tr>\n
H<\/span><\/td>\n+\/<\/span><\/td>\nABC*D\/EFI^^-G+H<\/span><\/td>\n<\/tr>\n
NULL<\/span><\/td>\nEmpty\u00a0<\/span><\/td>\nABC*D\/EFI^^-G+H\/+<\/b><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Thus, the outcome of the above expression in postfix is: ABC*D\/EFI^^-G+H\/+<\/strong><\/p>\n

Postfix evaluation:<\/h3>\n

The rules for postfix evaluation are:<\/p>\n

    \n
  • Whenever we encounter an operand, we push it into the stack.<\/li>\n
  • Whenever we encounter an operator in the postfix notation, we pop the top 2 elements out of the stack.<\/li>\n
  • The lower element i.e. the element at the position top-1 will be written first during evaluation.<\/li>\n<\/ul>\n

    For example: Let the postfix expression be 10 4 + 12 3 \/ *<\/p>\n\n\n\n\n\n\n\n\n\n\n
    Input\u00a0<\/strong><\/td>\nCurrent stack<\/strong><\/td>\nCurrent symbol<\/strong><\/td>\nOperations on stack<\/strong><\/td>\n<\/tr>\n
    10 4 + 12 3 \/ *<\/span><\/td>\nEmpty\u00a0<\/span><\/td>\n10<\/span><\/td>\nPush 10<\/span><\/td>\n<\/tr>\n
    4 + 12 3 \/ *<\/span><\/td>\n10<\/span><\/td>\n4<\/span><\/td>\nPush 4<\/span><\/td>\n<\/tr>\n
    + 12 3 \/ *<\/span><\/td>\n4, 10<\/span><\/td>\n+<\/span><\/td>\nPop 4,10 push 4+10<\/span><\/td>\n<\/tr>\n
    12 3 \/ *<\/span><\/td>\n14<\/span><\/td>\n12<\/span><\/td>\nPush 12<\/span><\/td>\n<\/tr>\n
    3 \/ *<\/span><\/td>\n14, 12<\/span><\/td>\n3<\/span><\/td>\nPush 3<\/span><\/td>\n<\/tr>\n
    \/ *<\/span><\/td>\n14, 12, 3<\/span><\/td>\n\/<\/span><\/td>\nPop 3, 12 and push 12\/3<\/span><\/td>\n<\/tr>\n
    *<\/span><\/td>\n14, 4<\/span><\/td>\n*<\/span><\/td>\nPop 4, 14 and push 4*14<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    The result of this postfix evaluation is: 56<\/p>\n

    Algorithm for expression parsing:<\/h3>\n

    Step 1:<\/strong> Scan all the symbols of the expression one by one.
    \nStep 2:<\/strong> If the input character is an operand, we push it into the stack.
    \nStep 3:<\/strong> If the input character is an operator, we pop it out and perform the relevant operation.
    \nStep 4:<\/strong> Push the result of the operation back into the stack.
    \nStep 5:<\/strong> Repeat steps 1 to 4 until we have performed all the operations.
    \nStep 6:<\/strong> Pop the stack. Perform the final operation.<\/p>\n

    Postfix evaluation in C++<\/h3>\n
    #include <bits\/stdc++.h>\nusing namespace std;\n \nint Precedence_Order(char opd){\n    if(opd == '+'||opd == '-')\n        return 1;\n    if(opd == '*'||opd == '\/')\n        return 2;\n    return 0;\n}\n \nint Operation(int num1, int num2, char opd){\n    switch(op){\n        case '+': return num1 + num2;\n        case '-': return num1 - num2;\n        case '*': return num1 * num2;\n        case '\/': return num1 \/ num2;\n    }\n}\n \nint Evaluate(string expression){\n    int i;\n     \n    stack <int> values;\n     \n    stack <char> ops;\n     \n    for(i = 0; i < expression.length(); i++){\n        \n        if(expression[i] == ' ')\n            continue;\n         \n        else if(expression[i] == '('){\n            ops.push(expression[i]);\n        }\n         \n        else if(isdigit(expression[i])){\n            int val = 0;\n             \n            while(i < expression.length() && isdigit(expression[i]))\n            {\n                val = (val*10) + (expression[i]-'0');\n                i++;\n            }\n             \n            values.push(val);\n             \n              i--;\n        }\n         \n       \n        else if(expression[i] == ')')\n        {\n            while(!ops.empty() && ops.top() != '(')\n            {\n                int val2 = values.top();\n                values.pop();\n                 \n                int val1 = values.top();\n                values.pop();\n                 \n                char opd = ops.top();\n                ops.pop();\n                 \n                values.push(Operation(val1, val2, opd));\n            }\n             \n            \n            if(!ops.empty())\n               ops.pop();\n        }\n         \n        \n        else\n        {\n            \n            while(!ops.empty() && Precedence_Order(ops.top())>= Precedence_Order(expression[i])){\n                int val2 = values.top();\n                values.pop();\n                 \n                int val1 = values.top();\n                values.pop();\n                 \n                char opd = ops.top();\n                ops.pop();\n                 \n                values.push(Operation(val1, val2, opd));\n            }\n             \n            \n            ops.push(expression[i]);\n        }\n    }\n     \n    \n    while(!ops.empty()){\n        int val2 = values.top();\n        values.pop();\n                 \n        int val1 = values.top();\n        values.pop();\n                 \n        char opd = ops.top();\n        ops.pop();\n                 \n        values.push(Operation(val1, val2, opd));\n    }\n     \n    \n    return values.top();\n}\n \nint main() {\n    cout << Evaluate(\"34 + 13 * 93\") << \"\\n\";\n    cout << Evaluate(\"85 \/ 23 - 16\") << \"\\n\";\n    cout << Evaluate(\"100 * ( 2 + 12 )\") << \"\\n\";\n    cout << Evaluate(\"121 * ( 5 - 1 ) \/ 11\");\n    return 0;\n}\n<\/pre>\n
    Expression parsing in Python:<\/h3>\n
    def Precedence_Order(opd):\n    \n    if opd == '+' or opd == '-':\n        return 1\n    if opd == '*' or opd == '\/':\n        return 2\n    return 0\n \ndef Operation(num1, num2, opd):\n     \n    if opd == '+': return num1 + num2\n    if opd == '-': return num1 - num2\n    if opd == '*': return num1 * num2\n    if opd == '\/': return num1 \/\/ num2\n \ndef Evaluate(expression):\n     \n    values = []\n    ops = []\n    i = 0\n     \n    while i < len(expression):\n         \n        if expression[i] == ' ':\n            i += 1\n            continue\n         \n        elif expression[i] == '(':\n            ops.append(expression[i])\n         \n        elif expression[i].isdigit():\n            val = 0\n             \n            while (i < len(expression) and\n                expression[i].isdigit()):\n             \n                val = (val * 10) + int(expression[i])\n                i += 1\n             \n            values.append(val)\n             \n            i-=1\n        \n        elif expression[i] == ')':\n         \n            while len(ops) != 0 and ops[-1] != '(':\n             \n                val2 = values.pop()\n                val1 = values.pop()\n                opd = ops.pop()\n                 \n                values.append(Operation(val1, val2, opd))\n            ops.pop()\n         \n        else:\n        \n            while (len(ops) != 0 and Precedence_Order(ops[-1]) >= Precedence_Order(expression[i])):\n                val2 = values.pop()\n                val1 = values.pop()\n                opd = ops.pop()\n                 \n                values.append(Operation(val1, val2, opd))\n             \n            \n            ops.append(expression[i])\n         \n        i += 1\n     \n    while len(ops) != 0:\n         \n        val2 = values.pop()\n        val1 = values.pop()\n        opd = ops.pop()\n                 \n        values.append(Operation(val1, val2, opd))\n     \n    return values[-1]\n \nif __name__ == \"__main__\":\n     \n    print(Evaluate(\"34 + 13 * 93\"))\n    print(Evaluate(\"85 \/ 23 - 16\"))\n    print(Evaluate(\"100 * ( 2 + 12 )\"))\n    print(Evaluate(\"121 * ( 5 - 1 ) \/ 11\"))\n<\/pre>\n
    Conclusion<\/h3>\n
    Expression parsing is a very important concept of data structures because it tells us how a compiler evaluates the arithmetic expressions. As mentioned earlier, it is difficult for a compiler to solve the expressions in infix notations which is why it converts the expression into postfix or prefix.<\/p>\n
    Thus, it is very important for us to understand what are postfix and prefix notations and how a compiler works on them or evaluates them.<\/p>\n","protected":false},"excerpt":{"rendered":"
    An expression is a statement that generates a value on evaluation. Parsing means analyzing a string or a set of symbols one by one depending on a particular criterion. Expression parsing a term used...<\/p>\n","protected":false},"author":1,"featured_media":81478,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[3649,3650,3651,3652,3653],"class_list":["post-81401","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-expression-parsing","tag-infix-notation","tag-infix-to-postfix-conversion","tag-postfix-notation","tag-prefix-notation"],"yoast_head":"\nExpression Parsing in Data Structure - TechVidvan<\/title>\n<meta name=\"description\" content=\"Learn about Expression parsing in data structure because it tells us how a compiler evaluates the arithmetic expressions.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Expression Parsing in Data Structure - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"Learn about Expression parsing in data structure because it tells us how a compiler evaluates the arithmetic expressions.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-07-01T03:30:53+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Expression-parsing.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"9 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Expression Parsing in Data Structure - TechVidvan","description":"Learn about Expression parsing in data structure because it tells us how a compiler evaluates the arithmetic expressions.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/","og_locale":"en_US","og_type":"article","og_title":"Expression Parsing in Data Structure - TechVidvan","og_description":"Learn about Expression parsing in data structure because it tells us how a compiler evaluates the arithmetic expressions.","og_url":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2021-07-01T03:30:53+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Expression-parsing.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"9 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Expression Parsing in Data Structure","datePublished":"2021-07-01T03:30:53+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/"},"wordCount":1412,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Expression-parsing.jpg","keywords":["Expression Parsing","Infix Notation","Infix to Postfix Conversion","Postfix Notation","Prefix Notation"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/","url":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/","name":"Expression Parsing in Data Structure - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Expression-parsing.jpg","datePublished":"2021-07-01T03:30:53+00:00","description":"Learn about Expression parsing in data structure because it tells us how a compiler evaluates the arithmetic expressions.","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Expression-parsing.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Expression-parsing.jpg","width":1200,"height":628,"caption":"Expression Parsing"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/expression-parsing-in-data-structure\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Expression Parsing in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/81401","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=81401"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/81401\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/81478"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=81401"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=81401"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=81401"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}