[BOJ] 6968 - Lottery

https://www.acmicpc.net/problem/6968

BOJ - Lottery

문제 유형: 문자열 처리, 그리디, 문자열 파싱, 구현

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 128MB

 

문제

You have just won the lottery. All that separates you from your multi-million dollar prize is your correct answer to the following skill-testing question:  1234+4567×11

In your twenty seconds you see your fortune slipping away because you don't know whether the answer is (1234+4567)×11=63811  or  1234+(4567×11)=51471

Finally you guess 63811, but that answer is incorrect. Your math teacher set the question and expected you to remember that multiplication is done before addition. The correct answer is 51471.

Your job is to write a program to insert parentheses into lottery questions such as the above so as to make clear the order of operations.

 

로또에 당첨 되셨습니다!

수백만 달러를 받기 위해서는, 당신의 다음과 같은 문제를 풀어야 합니다: 1234 + 4567 x 11.

주어진 수식의 순서를 명확하고 알맞게 정해주는 프로그램을 작성하시오.

 

입력

The input to your program consists of a line containing an integer, n, followed by n lines of input. Each of the n lines contains an expression consisting of integers, and the operators +, -, and X denoting addition, subtraction, and multiplication respectively. Adjacent integers are separated by one operator. There is a single space to the left and to the right of each operator and no input line contains more than 80 characters.

 

입력의 개수 n이 주어집니다.

각 n개의 줄에는 정수, +, -, X가 포함되어 있습니다.

+는 덧셈, -는 뺄셈, X는 곱셈을 의미합니다.

두 정수는 반드시 하나의 연산자로 구분됩니다.

모든 토큰간에는 공백으로 구분되어있고, 한 줄에 80글자를 넘지 않습니다.

 

출력

Your output should consist of the same n lines, with a blank line between them, with parentheses inserted in the n lines so as to indicate the order of operations. Multiplication should be done first, from left to right, and addition and subtraction should then be done from left to right. Spaces surrounding operators should be preserved.

 

n개의 정리된 수식을 출력하시오.

같은 우선순위의 연산자는 왼쪽우선으로 연산하도록 구성하시오.

각 답마다 공백으로 구분하시오.

 

풀이

만약 토큰 수가 3개 이하라면, 그대로 출력해야 한다.

 

곱셈기호를 기준으로 양쪽 숫자에 대해 미리 수식을 괄호로 묶어놓고,

순차적으로 왼쪽우선으로 괄호로 묶어준다.

마지막 수식에는 괄호를 묶을 필요 없으니, 1개의 수식으로 묶일때까지 묶는작업을 했다면, 양 끝을 벗겨주자.

deque를 이용해서 구현했다.

내 경우 곱셈 부분 파싱은 오른쪽 끝에서, +, - 묶기는 왼쪽 끝에서 이루어졌다.

 

입출력 형식에 주의하자.

C++의 경우, cin으로 처음 개수를 받고, cin.ignore()로 개행문자를 하나 날리고, 그 뒤부터 getline을 해야 한다.

Go의 경우, Readstring이 개행문자까지 가져오니 주의하자.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void solve() {
  string s;
  getline(cin, s);
  stringstream ss(s);

  deque<string> dq; // has expression
  vector<string> tokens;
  vector<char> ops;
  string temp;
  while (ss >> temp) {
    tokens.push_back(temp);
  }
  if (tokens.size() <= 3) {
    cout << s << "\n";
    return;
  }
  for (int i = 0; i < tokens.size(); ++i) {
    // is Number?
    string token = tokens[i];
    if (token[0] >= '0' && token[0] <= '9') {
      dq.push_back(token);
    } else if (token[0] == 'X') {
      auto operandA = dq.back();
      string operandB = tokens[i + 1];
      dq.pop_back();
      i++;
      dq.push_back("(" + operandA + " X " + operandB + ")");
    } else {
      ops.push_back(token[0]);
    }
  }

  int k = 0;
  while (k < ops.size()) {
    auto operandA = dq.front();
    dq.pop_front();
    auto operandB = dq.front();
    dq.pop_front();
    dq.push_front("(" + operandA + " " + ops[k] + " " + operandB + ")");
    k++;
  }

  cout << dq.front().substr(1, dq.front().size() - 2) << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin >> t;
  cin.ignore();
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
}

 

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

var (
	reader *bufio.Reader
	writer *bufio.Writer
)

func solve() {
	exp, _ := reader.ReadString('\n')
	tokens := strings.Fields(exp)
	dq := make([]string, 0)
	ops := make([]byte, 0)

	if len(tokens) <= 3 {
		fmt.Fprint(writer, exp)
		return
	}

	for i := 0; i < len(tokens); i++ {
		token := tokens[i]
		pref := token[0]
		if pref >= '0' && pref <= '9' {
			dq = append(dq, token)
		} else if pref == 'X' {
			operandA := dq[len(dq)-1]
			i++
			operandB := tokens[i]
			dq[len(dq)-1] = "(" + operandA + " X " + operandB + ")"
		} else {
			ops = append(ops, pref)
		}
	}

	k := 0
	for k < len(ops) {
		operandA := dq[0]
		operandB := dq[1]
		dq = dq[2:]
		newexp := "(" + operandA + " " + string(ops[k]) + " " + operandB + ")"
		dq = append([]string{newexp}, dq...)
		k++
	}
	fmt.Fprintln(writer, dq[0][1:len(dq[0])-1])
}

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int32
	fmt.Fscanln(reader, &t)
	for t > 0 {
		solve()
		t--
		if t > 0 {
			fmt.Fprintln(writer)
		}
	}
}