Expression Evaluation in C
Expression:
“A series of operators and operands that results in a single value is called an expression.”
For instance, the equation 10 + 5 becomes 15 when divided by two.
They are categorised into different sorts depending on the operators and operators that were utilised in the expression.
Among them are:
- Expressions with integers and operators are known as integer expressions.
- Real expressions are those that contain operators and floating-point values.
- Expressions with operands and arithmetic operators are referred to as arithmetic expressions.
- Mixed-mode arithmetic expressions are those that have both real and integer operands.
- Expressions that include relational operators and operands are referred to as relational expressions.
- Expressions that include logical operators and operands are known as logical expressions.
- Expressions used for assignments, etc. - Expressions with operands and assignment operators.
Associativity:
- There is a precedence (priority) assigned to each C operator.
- The evaluation of an expression containing multiple operators is controlled by this precedence.
- An operator may be a member of one of the many levels of operator precedence.
- The higher level of precedence operators are examined first. Depending on an operator's associativity property, the operators at the same level of precedence are evaluated either from right to left or from left to right.
- The precedence levels of the operators as well as the associativity of the operators within the same level are shown in the table below. The highest precedence is shown by Rank 14, while the lowest is indicated by Rank 0.
An Expression Evaluation Algorithm:
We now understand the problem statement for the evaluation of expressions.
So, without wasting any more time, we move on to the algorithms that will be used to solve the expression evaluation problem.
- Create an expression-filled string of length s at its beginning.
- Make two stacks: one for operators and the other for values.
- Check the current character to see if it's a white space before moving on to the next character in the string. Otherwise, push it into a stack of operators if it is an opening parenthesis.
- Unless the character being displayed is a number. Set an integer variable, val, to 0. While the current character is a digit, traverse from the current position + 1 to the end of the string and update the value as val * 10 + current digit. Put it on top of the values stack.
- Otherwise, traverse while the stack of operators is not empty and the current character in it is not an opening parenthesis if it is a closing parenthesis.
- Pick an operator from the operator stack and the top two digits from the value stack. Put the result of the math operation into a stack of values.
- Pop the top two digits from the value stack and an operator from the operator stack while the operator stack is still filled with values. Put the result of the math operation into a stack of values.
- A value at the top of the stack will be returned.
Program:
#include <bits/stdc++.h>
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);
}
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("100 * ( 2 + 12 )") << endl;
return 0;
}
OUTPUT:
![Expression Evaluation in C](https://static.tutorialandexample.com/c/expression-evaluation-in-c1.png)
Complexity Assessment:
Time Complexity:
O(n), where n is the length of the expression that will be evaluated, is the measure of time complexity.
Space Complexity:
Space complexity is O(n) since n characters must be stored there.