結果

問題 No.708 （＋ー）の式
コンテスト
ユーザー くれちー
提出日時 2019-08-08 14:30:31
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,802 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 30,080 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 19:32:39
合計ジャッジ時間 850 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <ctype.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define MAX_S_LEN 100

uint8_t shunting_yard_input_priority(char c) {
  if (isdigit(c))
    return 5;

  switch (c) {
    case '(':
      return 4;
    case '+':
    case '-':
      return 2;
    case ')':
      return 1;
    case '\0':
      return 0;
  }
}

uint8_t shunting_yard_stack_priority(char c) {
  if (isdigit(c))
    return 5;

  switch (c) {
    case '+':
    case '-':
      return 3;
    case '(':
      return 1;
    case '\0':
      return 0;
  }
}

void shunting_yard_operate(int64_t *l, char op, int64_t r) {
  switch (op) {
    case '+':
      *l += r;
      break;
    case '-':
      *l -= r;
      break;
  }
}

int64_t shunting_yard(const char input[], size_t input_len) {
  size_t input_pos = 0;

  int64_t output_stack[MAX_S_LEN];
  size_t output_stack_pos = 0;

  char stack[MAX_S_LEN];
  stack[0] = '\0';
  size_t stack_pos = 1;

  while (input_pos < input_len || stack_pos > 0) {
    uint8_t input_priority = shunting_yard_input_priority(input[input_pos]);
    uint8_t stack_priority = shunting_yard_stack_priority(stack[stack_pos - 1]);

    if (input_priority > stack_priority) {
      stack[stack_pos++] = input[input_pos++];
    } else if (input_priority < stack_priority) {
      char c = stack[--stack_pos];

      if (isdigit(c)) {
        output_stack[output_stack_pos++] = c - '0';
      } else {
        int64_t r = output_stack[--output_stack_pos];
        shunting_yard_operate(&output_stack[output_stack_pos - 1], c, r);
      }
    } else {
      --stack_pos;
      input_pos++;
    }
  }

  return output_stack[0];
}

int main(void) {
  char s[MAX_S_LEN];
  scanf("%s", s);

  int64_t ans = shunting_yard(s, strlen(s) + 1);
  printf("%" PRId64 "\n", ans);
}
0