C++ programming

[Benji2408]

Write a program that takes as input an arithmetic expression and should do the following:
1. Check that the expression is well-formed: that means the number of opening parenthesis ‘(‘ is equal to closing ones, the operands are numeric characters, the operators are +, -, * or /.
2. Build the expression tree based on the arithmetic expression. This will take into consideration the priority of some operators over the others. Each node in the tree has as value a number or a string. In particular, leaf nodes have number values while intermediary nodes have a string value.
3. Evaluate the outcome of the whole expression by traversing the tree (using one variant of depth-first search) starting with leaf nodes and evaluating each branch until you get the result.

[jonnin]

where is your code, and what was the question?

[Thomas1965]

https://www.geeksforgeeks.org/evaluation-of-expression-tree/

[Benji2408]

Yes, I do have my code! I have been working on it because it has a lot to work on.

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <array>

using namespace std;

int MyLine(char op){

if(op == '+'||op == '-')
return 1;

if(op == '*'||op == '/')

return 2;

return 0;
}

// Arithmetic Operation

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 MyItem){
int i;


stack <int> values;

stack <char> ops;

for(i = 0; i < MyItem.length(); i++){

// Whitespace
if(MyItem[i] == ' ')
continue;

// Opening character
else if(MyItem[i] == '('){
ops.push(MyItem[i]);
}

// Number Character
else if(isdigit(MyItem[i])){
int val = 0;

while(i < MyItem.length() &&
isdigit(MyItem[i]))
{
val = (val*10) + (MyItem[i]-'0');
i++;
}

values.push(val);
}

// Closing Character
else if(MyItem[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));
}

ops.pop();
}


else
{
while(!ops.empty() && MyLine(ops.top())
>= MyLine(MyItem[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(MyItem[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();
}

// Example with proofs, resulting 11

int main()
{

cout << evaluate("( ( ( 9 + 1 ) / 2 ) * 3 ) - 4");

return 0;
}

[salem c]

> Yes, I do have my code!
Really? For sure?
Because it looks an awful lot like this, save for you ripping out a few comments.
https://www.geeksforgeeks.org/expression-evaluation/

2. Build the expression tree based on the arithmetic expression. This will take into consideration the priority of some operators over the others. Each node in the tree has as value a number or a string. In particular, leaf nodes have number values while intermediary nodes have a string value.

The code you found builds an RPN stack.

You need to be building a tree, a snippet of which perhaps looks something like this.

  ../..
  |   |
  |   v
  v   2
..+..
|   | 
v   v
9   1

Your main needs to be like this, to match the terms of your assignment.

tree = parse("( ( ( 9 + 1 ) / 2 ) * 3 ) - 4");
cout << evaluate(tree);