यांडेक्स में साक्षात्कार कार्य

• en.wikipedia.org/wiki/Dynamic_array
• en.wikipedia.org/wiki/Hash_table
• en.wikipedia.org/wiki/B-tree
• en.wikipedia.org/wiki/Rb-tree
• en.wikipedia.org/wiki/Self-balancing_binary_search_tree
• en.wikipedia.org/wiki/Heap_(data_structure)
• en.wikipedia.org/wiki/Trie
• en.wikipedia.org/wiki/Skip_list
• en.wikipedia.org/wiki/Graph_(abstract_data_type)

• en.wikipedia.org/wiki/Heapsort
• en.wikipedia.org/wiki/Quicksort
• en.wikipedia.org/wiki/Radix_sort

#include <string>
#include <cassert>
#include <memory>
#include <stdexcept>
#include <vector>
#include <iostream>
#include <cstdio>

using namespace std;

struct Token {
        enum Type { value, operation, opening_bracket, closing_bracket};
        Type type;
        string text;
};

struct Tokenizer {
        //I am too lazy to write real tokenizer, it is very simple. I hope formula generator for fake tokenizer will be ok. 
public:
        Tokenizer() { content=generate(); pos=content.begin(); } ;
        const Token* peek() { return pos!=content.end() ?&*pos:0; } ;
        const Token* get() { if (pos!=content.end()) { cout << pos->text << " "; } return pos!=content.end()?&*pos++:0; } ;
private:
    vector<Token> generate(int level=0);
    
private:
        vector<Token>::iterator pos;
        vector<Token> content;
};

//To be honest using classes for expression parsing is a bit overkill, old style could save some code. 
class Expression;
typedef struct auto_ptr<Expression> ExpressionPtr;

//Represents abstract expression
class Expression {
public:
        Expression() {}
        virtual ~Expression() {}
        //actually this static parse functions should be constructor in most classes. I.e. this is violation of principle 'Resource Acquisition Is Initialization'.
        //but some functions return different classes depending on context, i.e. this is some kind of 'virtual constructor' (see Operation::parse for example)
        //so I made decision to make static construction function in all classes, just for uniformity
        static ExpressionPtr parse(Tokenizer& tokens);
        virtual float calc()=0;
        virtual void debug(string prefix)=0;
};


//Represents single value: for example 3.1415
class Value: public Expression {
public:
        Value() {}
        virtual ~Value() {}
        static bool isItYou(Tokenizer& tokens);
        static ExpressionPtr parse(Tokenizer& tokens);
        virtual float calc() { return _value; }
        virtual void debug(string prefix) { cout << prefix << "Value(" <<  calc() <<"): " << _value << endl; } 
protected:
        float _value;
};

//Represents operation: + or -
class Operation: public Expression {
public:
        Operation() {};
        virtual ~Operation() {}
        static ExpressionPtr parse(Tokenizer& tokens, ExpressionPtr& l);
        virtual float calc();
        virtual void debug(string prefix) { cout << prefix << "Operation(" <<  calc() <<"): " << _operation << endl; if ( _left.get() ) _left->debug(prefix + "\t"); if ( _right.get() ) _right->debug(prefix + "\t"); } 
protected:
        std::auto_ptr<Expression> _left;
        std::auto_ptr<Expression> _right;
        string _operation;
};

//Represents operation: * or /
class PriorityOperation: public Operation {
public:
        PriorityOperation() {};
        virtual ~PriorityOperation() {}
        static ExpressionPtr parse(Tokenizer& tokens, ExpressionPtr& left);
        //virtual float calc(); inherit it
        virtual void debug(string prefix) { cout << prefix << "PriorityOperation(" <<  calc() <<"): " << _operation << endl; if ( _left.get() ) _left->debug(prefix + "\t"); if ( _right.get() ) _right->debug(prefix + "\t"); } 
};


//Represents bracketed expression: (expr)
class BracketExpression: public Expression {
public:
        static bool isItYou(Tokenizer& tokens);
        static ExpressionPtr parse(Tokenizer& tokens);
        virtual float calc() { return _internal->calc(); } ;
        virtual void debug(string prefix) { cout << prefix << "Brackets(" <<  calc() <<"): "  << endl; _internal->debug(prefix + "\t"); } 
protected:
        std::auto_ptr<Expression> _internal; 
};


ExpressionPtr Expression::parse(Tokenizer& tokens)
{
    //cout << "Expression::parse" << endl;
    
        if (!tokens.peek()) return ExpressionPtr();

        if ( BracketExpression::isItYou(tokens) )
        {
                return BracketExpression::parse(tokens);
        }
        else
        if ( Value::isItYou(tokens) )
        {        
                return Value::parse(tokens);
        }
        else
        {
                throw logic_error("(Expression) Wtf is that: " + tokens.peek()->text );
        }
}

bool Value::isItYou(Tokenizer& tokens) 
{
        const Token* t = tokens.peek();
        if ( !t || t->type != Token::value ) return false; 

        char* endptr;
        strtod( t->text.c_str(), &endptr);
        return *endptr == 0;
}

ExpressionPtr Value::parse(Tokenizer& tokens)
{
    //cout << "Value::parse" << endl;
    
        std::auto_ptr<Value> foo( new Value );

        const Token* t=tokens.get();
        assert( t && t->type == Token::value ); 

        char* endptr;
        foo->_value = strtod( t->text.c_str(), &endptr);
        return ExpressionPtr(foo.release()); //lack of heterosexual auto_ptr conversions is killing me
}

bool BracketExpression::isItYou(Tokenizer& tokens) 
{
        return tokens.peek() && tokens.peek()->type == Token::opening_bracket;
}


ExpressionPtr BracketExpression::parse(Tokenizer& tokens)
{
    //cout << "BracketExpression::parse" << endl;
        const Token* t=tokens.get();
        assert ( t->type == Token::opening_bracket );

        auto_ptr<BracketExpression> result ( new BracketExpression );
        ExpressionPtr null;
        result->_internal = Operation::parse(tokens, null);

        t = tokens.get();
        if ( t ==0 || t->type != Token::closing_bracket )
        {
                throw logic_error("(BracketExpression) mismatched brackets ");
        }

        return ExpressionPtr(result.release());
}


ExpressionPtr Operation::parse(Tokenizer& tokens, ExpressionPtr& l)
{
    //cout << "Operation::parse:" << l.get() << endl;
        ExpressionPtr left;

        if (l.get()) 
        {
                left=l;
                // left is assigned for us.
        }
        else
        {
                left=Expression::parse(tokens);
        }        

        const Token *t=tokens.peek();
        if (!t || t->type == Token::closing_bracket  ) return left; //just return Value, sorry no operation guys

        if (t->type == Token::operation && (t->text=="*" || t->text=="/") )
        {
                ExpressionPtr result = PriorityOperation::parse(tokens, left);                 
                //we got exit after priority operations will end, parse position will be on + or - or at end
                left = result;        

                t=tokens.peek();
                if (!t || t->type == Token::closing_bracket  ) return left; //just return Value, sorry no operation guys
        }

    //cout << "Operation::parse again" << endl;
        if (t->type == Token::operation && (t->text=="+" || t->text=="-") )
        {
                tokens.get(); //just commit previous peek

                auto_ptr<Operation> result ( new Operation );
                result->_operation = t->text;
                result->_left=left; //smart ptr giveup ownership
        
        //cout << "Operation::parse before token" << endl;
        ExpressionPtr foo=Expression::parse(tokens);
        //cout << "Operation::parse after expression" << endl;
        
        const Token *t=tokens.peek();
        
        if (t != 0 && (t->text=="*" || t->text=="/"))
        {
            //cout << "Operation::parse to priority" << endl;
            foo = PriorityOperation::parse(tokens,foo);
        }
        
        result->_right=foo;
        
        ExpressionPtr bar(result.release());
        return Operation::parse(tokens, bar);
                
        }
        else
        {
                throw logic_error("(Operation) Wtf is that: " + tokens.peek()->text);
        }
}

ExpressionPtr PriorityOperation::parse(Tokenizer& tokens, ExpressionPtr& left)
{
    //cout << "PriorityOperation::parse" << endl;
    
    // left is already assigned for priority operation
        const Token *t=tokens.peek();
        if (!t || t->type == Token::closing_bracket  ) return left; //just return Value, sorry no operation guys

        if (t->type == Token::operation && (t->text=="*" || t->text=="/") )
        {
                tokens.get(); //commit previuos peek

                auto_ptr<PriorityOperation> result ( new PriorityOperation ); 
                result->_operation = t->text;
                result->_left=left;
                result->_right=Expression::parse(tokens);
                ExpressionPtr rs(result.release());

                return PriorityOperation::parse(tokens, rs);

        }
        else if (t->type == Token::operation && (t->text=="+" || t->text=="-") )
        {
                return left;
        }
        else
        {
                throw logic_error("(PriorityOperation) Wtf is that: " + tokens.peek()->text );
        }
}


float Operation::calc()
{
        if (_operation == "+")
        {
                float l=_left.get()?_left->calc():0.0f;
                float r=_right.get()?_right->calc():0.0f;
                return l+r;
        }
        else
        if (_operation == "-")
        {
                float l=_left.get()?_left->calc():0.0f;
                float r=_right.get()?_right->calc():0.0f;
                return l-r;
        }        
        else
        if (_operation == "*")
        {
                float l=_left.get()?_left->calc():1.0f;
                float r=_right.get()?_right->calc():1.0f;
                return  l*r; 
        }        
        else
        if (_operation == "/")
        {
                float l = _left.get()?_left->calc():1.0f;
                float r = _right.get()?_right->calc():1.0f;
                return l/r;
        }
        else
        {
                throw logic_error("Wft: operation udefined");
        }                
}

//returning vector by value, will be slow( O(n*n) actually ), but it is just testing code.
vector<Token> Tokenizer::generate(int level)
{
    //be careful with this value - formula size is approx 2^level
    if (level > 6)
    {
        Token t;
        char f[100];
        snprintf(f,100,"%d",int(rand() % 100));
        t.text=f;
        t.type=Token::value;
        return vector<Token>(&t,&t+1);
    }

    if (rand() % 10 == 0)
    {
            vector<Token> result;
            Token t1,t2;
            t1.type=Token::opening_bracket;
            t1.text="(";
            t2.type=Token::closing_bracket;
            t2.text=")";
            result.push_back(t1);
            vector<Token> r=generate(level+1);
            result.insert(result.end(),r.begin(),r.end());
            result.push_back(t2);

            return result;
    }        

    char op = "+-*/"[rand()%4];
    Token t;
    t.type=Token::operation;
    t.text=op;

    vector<Token> result=generate(level+1);
    result.push_back(t);
    vector<Token> r2=generate(level+1);
    result.insert(result.end(),r2.begin(),r2.end());

    return result;
}

int main()
{        
        try
        {
                //create fake tokenizer
                Tokenizer tk;

                //parse it
                ExpressionPtr null;
                ExpressionPtr foo = Operation::parse(tk,null);
                cout << endl;
                foo->debug("");
                float result = foo->calc();        
                cout << "result = " << result << endl;
        }
        catch(exception& e)
        {
                cout << e.what() << endl;
                return 1;                  
        }

        return 0;
}

#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>

struct token {
    enum { E_UNDEF, E_NUMBER, E_OPERATOR, E_LEVEL  } type;

    union {
        double d_val;
        int i_val;
        char c_val;
    } data;

    token() {
        type = E_UNDEF;
    }

    token(double val) : type(E_NUMBER) {
        data.d_val = val;
    }
    token(int val) : type(E_LEVEL) {
        data.i_val = val;
    }
    token(char val) : type(E_OPERATOR) {
        data.c_val = val;
    }
};

typedef std::vector<token> tokens;

void push_level(tokens &pr, int level) {
    if (pr.empty() || pr.back().type != token::E_LEVEL) {
        pr.push_back(token(level));
    } else {
        pr.back().data.i_val += level;
    }
}

void push_operator(tokens &pr, char op) {
    pr.push_back(token(op));
}

void push_number(tokens &pr, int num) {
    if (pr.empty() || pr.back().type == token::E_LEVEL || (pr.back().type == token::E_OPERATOR && pr.size() > 1 && pr[pr.size() - 2].type == token::E_NUMBER) ) {
        pr.push_back(token((double)num));
    } else if (pr.back().type == token::E_OPERATOR && (pr.size() == 1 || pr[pr.size() - 2].type == token::E_LEVEL) ) {
        if (pr.back().data.c_val == '*' || pr.back().data.c_val == '/') {
            throw std::domain_error("unexpected operator");
        }
        if (pr.back().data.c_val == '-') {
            num = -num;
        }
        pr.pop_back();
        pr.push_back(token((double)num));
    } else {
        throw std::domain_error("unexpected number");
    }
}

token calc3(tokens &pr) {
    token s2 = pr.back(); pr.pop_back();
    token op = pr.back(); pr.pop_back();
    token s1 = pr.back(); pr.pop_back();

    if (s1.type != token::E_NUMBER || op.type != token::E_OPERATOR || s2.type != token::E_NUMBER) {
        throw std::domain_error("unexpected closing brace");
    }

    switch (op.data.c_val) {
        case '+':
            s1.data.d_val += s2.data.d_val;
            break;
        case '-':
            s1.data.d_val -= s2.data.d_val;
            break;
        case '*':
            s1.data.d_val *= s2.data.d_val;
            break;
        case '/':
            s1.data.d_val /= s2.data.d_val;
            break;
        default:
        throw std::domain_error("internal error");
    }

    return s1;
}

void pop_level(tokens &pr, int level) {
    if (level == 0) {
        if (pr.size() > 3) {
            pr.push_back(calc3(pr));
        }
        return;
    }
    if (pr.empty() || pr.back().type == token::E_LEVEL || pr.back().type == token::E_OPERATOR) {
        throw std::domain_error("unexpected closing brace");
    } else if (pr.size() > 1 && pr[pr.size() - 2].type == token::E_LEVEL) {
        if (pr[pr.size() - 2].data.i_val > level) {
            pr[pr.size() - 2].data.i_val -= level;
        } else {
            int delta = level - pr[pr.size() - 2].data.i_val;
            token tmp = pr.back();
            pr.pop_back(); pr.pop_back();
            pr.push_back(tmp);
            pop_level(pr, delta);
        }
    } else if (pr.size() > 3) {
        token s1 = calc3(pr);

        if (pr.back().type == token::E_LEVEL) {
            if (pr.back().data.i_val > level) {
                pr.back().data.i_val -= level;
                pr.push_back(s1);
            } else {
                int delta = level - pr.back().data.i_val;
                pr.pop_back();
                pr.push_back(s1);
                pop_level(pr, delta);
            }
        } else if (pr.back().type == token::E_OPERATOR) {
            pr.push_back(s1);
            pop_level(pr, level);
        } else {
            throw std::domain_error("unexpected closing brace");
        }
    } else {
        throw std::domain_error("unexpected closing brace");
    }
}

double process(const std::string &str) {
    tokens program;

    push_level(program, 3);
    for (std::string::const_iterator cit = str.begin(); cit != str.end(); ++cit) {
        switch (*cit) {
            case '(':
                push_level(program, 3);
                break;
            case ')':
                pop_level(program, 3);
                break;
            case '*':
            case '/':
                pop_level(program, 1);
                push_operator(program, *cit);
                push_level(program, 1);
                break;
            case '+':
            case '-':
                if (cit == str.begin() || strchr("(+/-*", *(cit-1))) {
                    push_operator(program, *cit);
                } else {
                    pop_level(program, 2);
                    push_operator(program, *cit);
                    push_level(program, 2);
                }
                break;
            case ' ':
                break;
            case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
                {
                    int curnum = 0;
                    while (cit != str.end()) {
                        curnum = 10*curnum + (*cit - '0');
                        if ((cit + 1) == str.end() || !isdigit(*(cit+1))) {
                            break;
                        }
                        ++cit;
                    }
                    push_number(program, curnum);
                }
                break;
            default:
                throw std::domain_error("unexpected symbol");
        }
    }
    pop_level(program, 3);

    if (program.size() == 0 || program.size() > 1) {
        throw std::domain_error("incomplete expression");
    }

    return program.back().data.d_val;
}

int main() {
    std::string line;
    while (!std::cin.eof()) {
        std::getline(std::cin, line);

        if (line.length() > 0) {
            try {
                std::cout << process(line) << std::endl;
            } catch (std::exception &e) {
                std::cout << "error: " << e.what() << std::endl;
            }
        }
    }

    return 0;
}

• , « + = »
• , , «: »
• « ++»
• Scott Meyers. Effective C++. More Effective C++. Effective STL
• Herb Sutter «Exceptional C++» «More Exceptional C++»