Answer the question
In order to leave comments, you need to log in
How to solve a tree traversal problem?
Good afternoon.
Took part in the programming championship.
I want to know how to solve one problem. I'm not asking you to write a solution, but I would like to receive recommendations. What algorithms are used to solve such problems?
There may be links to resources where there are similar tasks. I will be very grateful.
Below conditions:
In 2158, the global organization UNP (United Programming Nations) passed an amnesty law. Within its framework, those convicted of not particularly serious crimes, capable of correcting programs important to the whole world, could avoid imprisonment. One of those given the opportunity, Jackie, was actually wrongly convicted, so he was allowed to make contact, but only with one random person. By chance, that person turned out to be you.
After spending several hours researching the problem he was given, Jackie came to the cause of the error. The whole point turned out to be the incorrect use of instances generated by the 'Q' object factory. The factory returns one instance if a string is passed to 'Q', and an array if an array of strings is passed to 'Q'. The instances returned in the array do not have the 'r' method, and therefore cannot be used in them, i.e. 'Q(['a'])[0].r()' is an error.
The code provided to him is quite large, but the time is short, and the 'r' method is called very often. Jackie needs to find the necessary places in the code automatically. Help me write a check that would find illegal uses of the 'r' method in the code (that is, in those instances that were generated by the 'Q' factory called with an array of strings).
It is known about the code passed by Jackie that:
it is written in es3,
variables get their values when declared and are not overwritten, i.e. there will be no such thing in the code as 'var a = x; a = y;' and 'var a = b = 1;',
access to object properties is possible both through a dot and through brackets ('ab' and 'a['b']'),
part of the expression can be stored in a variable, but never is passed to the function as a parameter ('a(x)' is forbidden),
there are no functions that return a part of the searched expression,
there are no properties of objects or array elements that contain a part of the expression,
when accessing a property of an object, the name of the property can be taken from the variable ( 'a[x]', x is a variable).
The check should be formatted as a CommonJS module that exports a function that takes an abstract syntax tree (ast) of the code being checked as input.
The function should return an array of ast nodes that correspond to the places where the 'r' method was called. The order of the elements in the array is not important, duplicates are not allowed.
Code that can be used as a basis for tree traversal:
link: https://codepen.io/alex-buki/pen/xxxgzbJ
Input data:
{
"type": "File",
"start": 0,
"end": 53,
"program": {
"type": "Program",
"start": 0,
"end": 53,
"sourceType": "script",
"interpreter": null,
"body": [
{
"type": "ExpressionStatement",
"start": 0,
"end": 25,
"expression": {
"type": "CallExpression",
"start": 0,
"end": 24,
"callee": {
"type": "MemberExpression",
"start": 0,
"end": 22,
"object": {
"type": "MemberExpression",
"start": 0,
"end": 10,
"object": {
"type": "CallExpression",
"start": 0,
"end": 7,
"callee": {
"type": "Identifier",
"start": 0,
"end": 1,
"name": "Q"
},
"arguments": [
{
"type": "ArrayExpression",
"start": 2,
"end": 6,
"elements": [
{
"type": "StringLiteral",
"start": 3,
"end": 5,
"extra": {
"rawValue": "",
"raw": "''"
},
"value": ""
}
]
}
]
},
"property": {
"type": "NumericLiteral",
"start": 8,
"end": 9,
"extra": {
"rawValue": 0,
"raw": "0"
},
"value": 0
},
"computed": true
},
"property": {
"type": "Identifier",
"start": 21,
"end": 22,
"name": "r"
},
"computed": false
},
"arguments": []
}
},
{
"type": "ExpressionStatement",
"start": 27,
"end": 52,
"expression": {
"type": "CallExpression",
"start": 27,
"end": 51,
"callee": {
"type": "MemberExpression",
"start": 27,
"end": 49,
"object": {
"type": "MemberExpression",
"start": 27,
"end": 37,
"object": {
"type": "CallExpression",
"start": 27,
"end": 34,
"callee": {
"type": "Identifier",
"start": 27,
"end": 28,
"name": "Q"
},
"arguments": [
{
"type": "ArrayExpression",
"start": 29,
"end": 33,
"elements": [
{
"type": "StringLiteral",
"start": 30,
"end": 32,
"extra": {
"rawValue": "",
"raw": "''"
},
"value": ""
}
]
}
]
},
"property": {
"type": "NumericLiteral",
"start": 35,
"end": 36,
"extra": {
"rawValue": 0,
"raw": "0"
},
"value": 0
},
"computed": true
},
"property": {
"type": "Identifier",
"start": 48,
"end": 49,
"name": "m"
},
"computed": false
},
"arguments": []
}
}
],
"directives": []
}
}
[
{
"type": "Identifier",
"start": 21,
"end": 22,
"name": "r"
}
]
Answer the question
In order to leave comments, you need to log in
the menu has a border-bottom, it just doesn't fit into the block
https://habr.com/en/company/jugru/blog/428628/
Maybe someone is interested, the article has a lot of useful information for solving this problem.
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question