Алгоритм сортировочной станции: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «{| width="100%" | width=50% | vector<string> toPostfix(string &s) { vector<string> postfix, stack; string number; for (char c : s) {...»)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
{| width="100%"
== Арифметические действия ==
| width=50% |
 
  vector<string> toPostfix(string &s) {
  vector<string> toPostfix(string &s) {
     vector<string> postfix, stack;
     vector<string> postfix, stack;
Строка 14: Строка 14:
             }
             }
             if (!isspace(c)) {
             if (!isspace(c)) {
                 while (!stack.empty() &&
                 while (!stack.empty() && (c == '+' || c == '-' || stack.back() == "*" || stack.back() == "/")) {
                        (c == '+' || c == '-' || stack.back() == "*" || stack.back() == "/")) {
                     postfix.push_back(stack.back());
                     postfix.push_back(stack.back());
                     stack.pop_back();
                     stack.pop_back();
Строка 30: Строка 29:
     return postfix;
     return postfix;
  }
  }
| width="10px" | &nbsp;
 
| width=50% |
== Арифметические действия, скобки ==
 
vector<string> toPostfix(string &s) {
    vector<string> postfix, stack;
    string number;
   
    for (char c : s) {
        if (isdigit(c)) {
            number += c;
        } else {
            if (!number.empty()) {
                postfix.push_back(number);
                number.clear();
            }
           
            if (c == '(') {
                stack.push_back(string(1, c));
            } else if (c == ')') {
                while (stack.back() != "(") {
                    postfix.push_back(stack.back());
                    stack.pop_back();
                }
                stack.pop_back();
            } else if (!isspace(c)) {
                while (!stack.empty() && stack.back() != "(" && (c == '+' || c == '-' || stack.back() == "*" || stack.back() == "/")) {
                    postfix.push_back(stack.back());
                    stack.pop_back();
                }
                stack.push_back(string(1, c));
            }
        }
    }
   
    if (!number.empty())
        postfix.push_back(number);
    postfix.insert(postfix.end(), stack.rbegin(), stack.rend());
   
    return postfix;
}
 
== Вычисление значения выражения в постфиксной записи ==
 
  int eval(const vector<string> &postfix) {
  int eval(const vector<string> &postfix) {
     vector<int> stack;
     vector<int> stack;
Строка 56: Строка 96:
     return stack.back();
     return stack.back();
  }
  }
|}


==Ссылки==
==Ссылки==
*[https://en.wikipedia.org/wiki/Shunting_yard_algorithm en.wikipedia.org — Shunting_yard_algorithm]
*[https://en.wikipedia.org/wiki/Shunting_yard_algorithm en.wikipedia.org — Shunting_yard_algorithm]
[[Category: Разбор выражений]]

Текущая версия от 19:36, 13 февраля 2023

Арифметические действия

vector<string> toPostfix(string &s) {
    vector<string> postfix, stack;
    string number;
    
    for (char c : s) {
        if (isdigit(c)) {
            number += c;
        } else {
            if (!number.empty()) {
                postfix.push_back(number);
                number.clear();
            }
            if (!isspace(c)) {
                while (!stack.empty() && (c == '+' || c == '-' || stack.back() == "*" || stack.back() == "/")) {
                    postfix.push_back(stack.back());
                    stack.pop_back();
                }
                stack.push_back(string(1, c));
            }
        }
    }
    
    if (!number.empty())
        postfix.push_back(number);
    postfix.insert(postfix.end(), stack.rbegin(), stack.rend());
    
    return postfix;
}

Арифметические действия, скобки

vector<string> toPostfix(string &s) {
    vector<string> postfix, stack;
    string number;
    
    for (char c : s) {
        if (isdigit(c)) {
            number += c;
        } else {
            if (!number.empty()) {
                postfix.push_back(number);
                number.clear();
            }
            
            if (c == '(') {
                stack.push_back(string(1, c));
            } else if (c == ')') {
                while (stack.back() != "(") {
                    postfix.push_back(stack.back());
                    stack.pop_back();
                }
                stack.pop_back();
            } else if (!isspace(c)) {
                while (!stack.empty() && stack.back() != "(" && (c == '+' || c == '-' || stack.back() == "*" || stack.back() == "/")) {
                    postfix.push_back(stack.back());
                    stack.pop_back();
                }
                stack.push_back(string(1, c));
            }
        }
    }
    
    if (!number.empty())
        postfix.push_back(number);
    postfix.insert(postfix.end(), stack.rbegin(), stack.rend());
    
    return postfix;
}

Вычисление значения выражения в постфиксной записи

int eval(const vector<string> &postfix) {
    vector<int> stack;
    
    for (const string &token : postfix) {
        if (isdigit(token[0])) {
            stack.push_back(stoi(token));
        } else {
            int b = stack.back();
            stack.pop_back();
            int &a = stack.back();
            
            if (token == "+")
                a += b;
            else if (token == "-")
                a -= b;
            else if (token == "*")
                a *= b;
            else
                a /= b;
        }
    }

    return stack.back();
}

Ссылки