ACM 문제 풀이 길 (11) 더미, 스 택, 대기 열 표현 식 변환
3629 단어 ACM 프로 그래 밍 경연 대회
제목: 표현 식 변환
산술 표현 식 은 접두사 표현법, 접두사 표현법 과 접두사 표현법 등 형식 이 있다.일상적으로 사용 하 는 산술 표현 식 은 두 개의 연산 수 중간 에 있 는 접두사 표현법, 즉 이원 연산 자 를 사용한다.디자인 프로그램 에서 접미사 표현 식 을 접미사 표현 식 으로 변환 하 십시오.
입력 형식:
한 줄 에 빈 칸 이 없 는 접두사 표현 식 을 입력 하 십시오.
출력 형식:
한 줄 에서 변 환 된 접미사 표현 식 을 출력 하려 면 서로 다른 대상 (연산 수, 연산 기호) 사이 에 빈 칸 으로 구분 해 야 하지만 끝 에 빈 칸 이 있어 서 는 안 됩 니 다.
입력 예시:
2+3*(7-4)+8/4
출력 예시:
2 3 7 4 - * + 8 4 / +
예 를 들 어 a + b * c + (d * e + f) * g
string 형식 읽 기
알파벳 을 만나면 바로 대기 열 에 들 어 갑 니 다.
곱셈 나 누 기 우선 순위 가 가감 법보 다 높다
우선 순위 높 은 입 소
우선 순위 가 같 거나 낮은 것 은 먼저 높 은 것 을 대열 에 넣 은 다음 에 현재 의 것 을 창고 에 넣 습 니 다.
하면, 만약, 만약...
')' 를 만나면 스 택 에서 '(') 를 찾 을 때 까지 머리 를 찾 고 스 택 에 있 는 '(') 을 삭제 합 니 다.
#include
#include
#include
#include
using namespace std;
int main(){
stack s1;
queue q1;
while (!s1.empty())
s1.pop();//
while (!q1.empty())
q1.pop();//
string s;
getline(cin, s);//
int len = s.size(), num = 0, i, j;
for (i = 0; i < len; i++){
string ts = "";
char c = s[i], prc = s[i - 1];//c prc
if ((c == '+' || c == '-') && (!i || prc == '(') || (c >= '0' && c <= '9'))
{//
if (c != '+') ts += c;
while (s[i + 1] == '.' || s[i + 1] >= '0' && s[i + 1] <= '9')//
ts += s[++i];// ts string
q1.push(ts);//
}
else if (c == '+' || c == '-')
{
int flag = 1;//flag (-4)
while (flag)
{
if (s1.empty() || s1.top() == "(")// (-4)
s1.push(ts + c), flag = 0;// ,
else
{
q1.push(s1.top());// , ,
s1.pop();
}
}
}
else if (c == '*' || c == '/')
{
int flag = 1;
while (flag)
{
if (s1.empty() || s1.top() == "(" || s1.top() == "+" || s1.top() == "-")
s1.push(ts + c), flag = 0;// ,
else
{
q1.push(s1.top());//
s1.pop();
}
}
}
else if (c == '(')//
s1.push(ts + c);
else if (c == ')')//
{
int flag = 1;
while (flag)
{
string tp = s1.top();
if (tp == "(") s1.pop(), flag = 0;//
else
{
q1.push(s1.top());//
s1.pop();
}
}
}
}
while (!s1.empty())
{
q1.push(s1.top());//
s1.pop();
}
if (!q1.empty())
{ //c_str() string C
printf("%s", q1.front().c_str()); q1.pop();
}// string %s
while (!q1.empty())
{
printf(" %s", q1.front().c_str()); q1.pop();
}
puts("");
return 0;
}