// 你需要在代码中 #include "utility.h"
// 你可以使用这个模板库的函数
#pragma once

#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#include "utility.h"
namespace sjtu {

template <typename... Args>
std::string format(std::string_view fmt, Args &&...args) {
  std::vector<std::string> vec = make_string(std::forward<Args>(args)...);
  std::string ret;
  std::vector<int> arg_seq;
  std::vector<std::string> str_seq;
  std::stack<int> stk;
  std::stringstream ss;
  std::stringstream pos_ss;
  for (int i = 0; i < fmt.length(); i++) {
    if (fmt[i] == '{') {
      if (stk.size() >= 2) throw std::runtime_error("invalid format string");
      if (stk.size() == 0)
        stk.push(i);
      else {
        int pl = stk.top();
        stk.pop();
        if (pl + 1 == i) {
          ss << '{';
        } else
          throw std::runtime_error("invalid format string");
      }
    } else if (fmt[i] == '}') {
      if (stk.size() != 1) throw std::runtime_error("invalid format string");
      stk.pop();
      str_seq.emplace_back("");
      str_seq[str_seq.size() - 1] = ss.str();
      // std::cerr << "get str token: " << str_seq[str_seq.size() - 1]
      //           << std::endl;
      int ps = -1;
      if (!(pos_ss >> ps)) ps = -1;
      arg_seq.emplace_back(ps);
      ss.clear();
      ss.str("");
      pos_ss.clear();
      pos_ss.str("");
    } else {
      if (stk.size() >= 2) throw std::runtime_error("invalid format string");
      if (stk.size() == 0)
        ss << fmt[i];
      else {
        if (fmt[i] < '0' || fmt[i] > '9')
          throw std::runtime_error("invalid format string");
        pos_ss << fmt[i];
      }
    }
  }
  std::string tmp;
  tmp = ss.str();
  str_seq.emplace_back(tmp);
  ss.clear();
  ss.str("");
  bool auto_pos = true;
  for (int i = 0; i < arg_seq.size(); i++) {
    if (arg_seq[i] >= 0) auto_pos = false;
  }
  for (int i = 0; i < arg_seq.size(); i++) {
    if (auto_pos && arg_seq[i] >= 0)
      throw std::runtime_error("invalid format string");
    if ((!auto_pos) && arg_seq[i] == -1)
      throw std::runtime_error("invalid format string");
  }
  // std::cerr << "argsize=" << arg_seq.size() << std::endl;
  // std::cerr << "str_size=" << str_seq.size() << std::endl;
  if (auto_pos)
    for (int i = 0; i < arg_seq.size(); i++) {
      arg_seq[i] = i;
    }
  for (int i = 0; i < arg_seq.size(); i++) {
    if (arg_seq[i] >= vec.size())
      throw std::runtime_error("invalid format string");
  }
  for (int i = 0; i < arg_seq.size(); i++) {
    ss << str_seq[i];
    ss << vec[arg_seq[i]];
  }
  ss << str_seq[str_seq.size() - 1];
  ret = ss.str();
  return ret;
}
}  // namespace sjtu