-
[Python] ๋ฐฑ์ค - 1918 ํ์ ํ๊ธฐ์__Python/__Algorithm 2022. 3. 24. 14:39
๋ฌธ์
https://www.acmicpc.net/problem/1918
๐น ๋ฌธ์
์์์ ์ผ๋ฐ์ ์ผ๋ก 3๊ฐ์ง ํ๊ธฐ๋ฒ์ผ๋ก ํํํ ์ ์๋ค. ์ฐ์ฐ์๊ฐ ํผ์ฐ์ฐ์ ๊ฐ์ด๋ฐ ์์นํ๋ ์ค์ ํ๊ธฐ๋ฒ(์ผ๋ฐ์ ์ผ๋ก ์ฐ๋ฆฌ๊ฐ ์ฐ๋ ๋ฐฉ๋ฒ์ด๋ค), ์ฐ์ฐ์๊ฐ ํผ์ฐ์ฐ์ ์์ ์์นํ๋ ์ ์ ํ๊ธฐ๋ฒ(prefix notation), ์ฐ์ฐ์๊ฐ ํผ์ฐ์ฐ์ ๋ค์ ์์นํ๋ ํ์ ํ๊ธฐ๋ฒ(postfix notation)์ด ๊ทธ๊ฒ์ด๋ค. ์๋ฅผ ๋ค์ด ์ค์ ํ๊ธฐ๋ฒ์ผ๋ก ํํ๋ a+b๋ ์ ์ ํ๊ธฐ๋ฒ์ผ๋ก๋ +ab์ด๊ณ , ํ์ ํ๊ธฐ๋ฒ์ผ๋ก๋ ab+๊ฐ ๋๋ค.
์ด ๋ฌธ์ ์์ ์ฐ๋ฆฌ๊ฐ ๋ค๋ฃฐ ํ๊ธฐ๋ฒ์ ํ์ ํ๊ธฐ๋ฒ์ด๋ค. ํ์ ํ๊ธฐ๋ฒ์ ์์์ ๋งํ ๋ฒ๊ณผ ๊ฐ์ด ์ฐ์ฐ์๊ฐ ํผ์ฐ์ฐ์ ๋ค์ ์์นํ๋ ๋ฐฉ๋ฒ์ด๋ค. ์ด ๋ฐฉ๋ฒ์ ์ฅ์ ์ ๋ค์๊ณผ ๊ฐ๋ค. ์ฐ๋ฆฌ๊ฐ ํํ ์ฐ๋ ์ค์ ํ๊ธฐ์ ๊ฐ์ ๊ฒฝ์ฐ์๋ ๋ง์ ๊ณผ ๊ณฑ์ ์ ์ฐ์ ์์์ ์ฐจ์ด๊ฐ ์์ด ์ผ์ชฝ๋ถํฐ ์ฐจ๋ก๋ก ๊ณ์ฐํ ์ ์์ง๋ง ํ์ ํ๊ธฐ์์ ์ฌ์ฉํ๋ฉด ์์๋ฅผ ์ ์ ํ ์กฐ์ ํ์ฌ ์์๋ฅผ ์ ํด์ค ์ ์๋ค. ๋ํ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ๊ดํธ ๋ฑ๋ ํ์ ์๊ฒ ๋๋ค. ์๋ฅผ ๋ค์ด a+b*c๋ฅผ ํ์ ํ๊ธฐ์์ผ๋ก ๋ฐ๊พธ๋ฉด abc*+๊ฐ ๋๋ค.
์ค์ ํ๊ธฐ์์ ํ์ ํ๊ธฐ์์ผ๋ก ๋ฐ๊พธ๋ ๋ฐฉ๋ฒ์ ๊ฐ๋จํ ์ค๋ช ํ๋ฉด ์ด๋ ๋ค. ์ฐ์ ์ฃผ์ด์ง ์ค์ ํ๊ธฐ์์ ์ฐ์ฐ์์ ์ฐ์ ์์์ ๋ฐ๋ผ ๊ดํธ๋ก ๋ฌถ์ด์ค๋ค. ๊ทธ๋ฐ ๋ค์์ ๊ดํธ ์์ ์ฐ์ฐ์๋ฅผ ๊ดํธ์ ์ค๋ฅธ์ชฝ์ผ๋ก ์ฎ๊ฒจ์ฃผ๋ฉด ๋๋ค.
์๋ฅผ ๋ค์ด a+b*c๋ (a+(b*c))์ ์๊ณผ ๊ฐ๊ฒ ๋๋ค. ๊ทธ ๋ค์์ ์์ ์๋ ๊ดํธ์ ์ฐ์ฐ์ *๋ฅผ ๊ดํธ ๋ฐ์ผ๋ก ๊บผ๋ด๊ฒ ๋๋ฉด (a+bc*)๊ฐ ๋๋ค. ๋ง์ง๋ง์ผ๋ก ๋ +๋ฅผ ๊ดํธ์ ์ค๋ฅธ์ชฝ์ผ๋ก ๊ณ ์น๋ฉด abc*+๊ฐ ๋๊ฒ ๋๋ค.
๋ค๋ฅธ ์๋ฅผ ๋ค์ด ๊ทธ๋ฆผ์ผ๋ก ํํํ๋ฉด A+B*C-D/E๋ฅผ ์์ ํ๊ฒ ๊ดํธ๋ก ๋ฌถ๊ณ ์ฐ์ฐ์๋ฅผ ์ด๋์ํฌ ์ฅ์๋ฅผ ํ์ํ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ๋๋ค.
๊ฒฐ๊ณผ: ABC*+DE/-
์ด๋ฌํ ์ฌ์ค์ ์๊ณ ์ค์ ํ๊ธฐ์์ด ์ฃผ์ด์ก์ ๋ ํ์ ํ๊ธฐ์์ผ๋ก ๊ณ ์น๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค
๐น ์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ค์ ํ๊ธฐ์์ด ์ฃผ์ด์ง๋ค. ๋จ ์ด ์์์ ํผ์ฐ์ฐ์๋ ์ํ๋ฒณ ๋๋ฌธ์๋ก ์ด๋ฃจ์ด์ง๋ฉฐ ์์์์ ํ ๋ฒ์ฉ๋ง ๋ฑ์ฅํ๋ค. ๊ทธ๋ฆฌ๊ณ -A+B์ ๊ฐ์ด -๊ฐ ๊ฐ์ฅ ์์ ์ค๊ฑฐ๋ AB์ ๊ฐ์ด *๊ฐ ์๋ต๋๋ ๋ฑ์ ์์์ ์ฃผ์ด์ง์ง ์๋๋ค. ํ๊ธฐ์์ ์ํ๋ฒณ ๋๋ฌธ์์ +, -, *, /, (, )๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ๊ธธ์ด๋ 100์ ๋์ง ์๋๋ค.
๐น ์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํ์ ํ๊ธฐ์์ผ๋ก ๋ฐ๋ ์์ ์ถ๋ ฅํ์์ค
ํ์ด ๋ฐฉ๋ฒ
๐น ์คํ
๐น ๋์ ๊ณผ์
x(ํ์ฌ ๋ฌธ์) s(stack) ans(์ถ๋ ฅํ ๋ฌธ์์ด) A [ ] A * [ * ] A ( [ *,( ] A B [ *,( ] AB + [ *,(,+ ] AB C [ *,(,+ ] ABC ) [ * ] ABC+ [ ] ABC+* ๊ตฌํ ์ฝ๋
import sys prefix = list(sys.stdin.readline().strip()) ans = '' s = [] for x in prefix: if x.isalpha(): ans += x elif x == '(': s.append(x) elif x == ')': while s[-1] != '(': ans += s.pop() s.pop() elif x == '+' or x == '-': while s and s[-1] != '(': ans+=s.pop() s.append(x) elif x == '*' or x == '/': while s and (s[-1]== '*' or s[-1]=='/'): ans += s.pop() s.append(x) while s: ans+=s.pop() print(ans)
์คํ ๊ฒฐ๊ณผ
๐ก
728x90'__Python > __Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] ๋ฐฑ์ค - 1018 ์ฒด์คํ ๋ค์ ์น ํ๊ธฐ (1) 2022.03.25 [Python] ๋ฐฑ์ค - 11723 ์งํฉ (0) 2022.03.24 [Python] ๋ฐฑ์ค - 2559 ์์ด (0) 2022.03.24 [Python] ๋ฐฑ์ค - 1952 ๋ฌํฝ์ด 2 (0) 2022.03.24 [Python] ๋ฐฑ์ค - 1913 ๋ฌํฝ์ด(๊ธฐ์ด ๋ฐฐ์ด๋ค๋ฃจ๊ธฐ) (0) 2022.03.24