Expression Evaluation | CPP program to evaluate a given expression where tokens are separated by space . ; Function to find precedence of operators . ; Function to perform arithmetic operations . ; Function that returns value of expression after evaluation . ; stack to store integer values . ; stack to store operators . ; Current token is a whitespace , skip it . ; Current token is an opening brace , push it to ' ops ' ; Current token is a number , push it to stack for numbers . ; There may be more than one digits in number . ; right now the i points to the character next to the digit , since the for loop also increases the i , we would skip one token position ; we need to decrease the value of i by 1 to correct the offset . ; Closing brace encountered , solve entire brace . ; pop opening brace . ; Current token is an operator . ; While top of ' ops ' has same or greater precedence to current token , which is an operator . Apply operator on top of ' ops ' to top two elements in values stack . ; Push current token to ' ops ' . ; Entire expression has been parsed at this point , apply remaining ops to remaining values . ; Top of ' values ' contains result , return it . ; Driver method to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; int precedence ( char op ) { if ( op == ' + ' op == ' - ' ) return 1 ; if ( op == ' * ' op == ' / ' ) return 2 ; return 0 ; } int applyOp ( int a , int b , char op ) { switch ( op ) { case ' + ' : return a + b ; case ' - ' : return a - b ; case ' * ' : return a * b ; case ' / ' : return a / b ; } } int evaluate ( string tokens ) { int i ; stack < int > values ; stack < char > ops ; for ( i = 0 ; i < tokens . length ( ) ; i ++ ) { if ( tokens [ i ] == ' ▁ ' ) continue ; else if ( tokens [ i ] == ' ( ' ) { ops . push ( tokens [ i ] ) ; } else if ( isdigit ( tokens [ i ] ) ) { int val = 0 ; while ( i < tokens . length ( ) && isdigit ( tokens [ i ] ) ) { val = ( val * 10 ) + ( tokens [ i ] - '0' ) ; i ++ ; } values . push ( val ) ; i -- ; } else if ( tokens [ i ] == ' ) ' ) { while ( ! ops . empty ( ) && ops . top ( ) != ' ( ' ) { int val2 = values . top ( ) ; values . pop ( ) ; int val1 = values . top ( ) ; values . pop ( ) ; char op = ops . top ( ) ; ops . pop ( ) ; values . push ( applyOp ( val1 , val2 , op ) ) ; } if ( ! ops . empty ( ) ) ops . pop ( ) ; } else { while ( ! ops . empty ( ) && precedence ( ops . top ( ) ) >= precedence ( tokens [ i ] ) ) { int val2 = values . top ( ) ; values . pop ( ) ; int val1 = values . top ( ) ; values . pop ( ) ; char op = ops . top ( ) ; ops . pop ( ) ; values . push ( applyOp ( val1 , val2 , op ) ) ; } ops . push ( tokens [ i ] ) ; } } while ( ! ops . empty ( ) ) { int val2 = values . top ( ) ; values . pop ( ) ; int val1 = values . top ( ) ; values . pop ( ) ; char op = ops . top ( ) ; ops . pop ( ) ; values . push ( applyOp ( val1 , val2 , op ) ) ; } return values . top ( ) ; } int main ( ) { cout << evaluate ( "10 ▁ + ▁ 2 ▁ * ▁ 6" ) << " STRNEWLINE " ; cout << evaluate ( "100 ▁ * ▁ 2 ▁ + ▁ 12" ) << " STRNEWLINE " ; cout << evaluate ( "100 ▁ * ▁ ( ▁ 2 ▁ + ▁ 12 ▁ ) " ) << " STRNEWLINE " ; cout << evaluate ( "100 ▁ * ▁ ( ▁ 2 ▁ + ▁ 12 ▁ ) ▁ / ▁ 14" ) ; return 0 ; }