C 데이터 구조의 창고 응용: 괄호 일치 와 간단 한 계산기
5136 단어 C 언어 프로 그래 밍
1. 일치 하지 않 는 좌우 괄호 를 찾 아 원 문자열 을 출력 하고 어 울 리 지 않 는 왼쪽 괄호 아래 치기 &, 오른쪽 괄호 아래 치기?여러 그룹의 데 이 터 를 포함 하고 각 그룹의 데이터 한 줄 에 하나의 문자열 을 포함 하 며 좌우 괄호 와 대소 문자 만 포함 하고 문자 의 길 이 는 100 을 초과 하지 않 습 니 다.
샘플 입력) (rttyy () sss) (
샘플 출력 )(rttyy())sss)(
？ ? $
괄호 일치: 모든 오른쪽 괄호 때문에 이전에 일치 하지 않 았 던 왼쪽 괄호 중 가장 오른쪽 에 있 는 것 과 일치 합 니 다. 만약 우리 가 왼쪽 에서 오른쪽으로 문자열 을 옮 겨 다 니 며 만 나 는 왼쪽 괄호 를 스 택 에 넣 고 일치 하 기 를 기다 리 고 있 습 니 다. 옮 겨 다 니 는 과정 에서 오른쪽 괄호 를 만나면 스 택 이 비어 있 으 면 일치 하지 않 습 니 다. 그렇지 않 으 면 스 택 의 왼쪽 괄호 는 일치 하 는 왼쪽 괄호 입 니 다.
#include
#include
#include
using namespace std;
stack S;
char str[110];//
char ans[110];//
int main()
{
while(scanf("%s",str)!=EOF)//
{
int i;
for(i=0;str[i]!=0;i++)//
{
if(str[i]=='(')//
{
S.push(i);//
ans[i]=' ';//
}
else if(str[i]==')')//
{
if(S.empty()==false)//
{
S.pop();// ，
ans[i]=' ';
}
else
ans[i]='?';// ， ？
}
else
ans[i]=' ';// ，
}
while(!S.empty())// ，
{
ans[S.top()]='$';// $
S.pop();
}
ans[i]=0;// ， 0
puts(str);
puts(ans);
}
return 0;
} 괄호 매 칭 은 왼쪽 에서 오른쪽으로 문자열 을 옮 겨 다 닐 때 스 택 맨 위 에 있 는 왼쪽 괄호 가 현재 위치 에서 가장 가 까 운 특성 을 이용 하여 작업 을 완성 합 니 다.
2. 간단 한 계산기: + - * / 만 포함 하 는 비 마이너스 정수 계산 표현 식 을 읽 고 이 표현 식 의 값 입력 을 계산 합 니 다. 각 테스트 사례 는 한 줄 을 차지 하고 줄 마다 200 자 를 초과 하지 않 으 며 정수 와 연산 자 는 빈 칸 으로 구 분 됩 니 다.
한 줄 이 0 일 때 입력 이 끝 납 니 다. 1 + 2 4 + 2 * 5 - 7 / 11 0 출력 3.00 13.36
생각:
1. 창고 두 개, 저장 연산 자 하나, 저장 숫자 하나 설치
2. 표현 식 의 맨 끝 에 태그 연산 자 를 추가 합 니 다. 우선 순위 가 가장 낮 습 니 다.
3. 왼쪽 에서 오른쪽으로 문자열 을 옮 겨 다 니 며 연산 자 에 옮 겨 다 니 면 연산 자 스 택 상단 요소 와 비교 하면 스 택 상단 우선 순위 가 이 연산 자 보다 작 거나 이때 연산 자 스 택 은? 비어 있 습 니 다. 이 연산 자 는 스 택 에 들 어 갑 니 다. 다음 요 소 를 옮 겨 다 닙 니 다.
4. 스 택 꼭대기 연산 자가 이 연산 자 보다 크 면 스 택 꼭대기 요 소 를 팝 업 하고 두 개의 숫자 를 팝 업 하여 계산 한 다음 에 계산 결 과 를 스 택 에 넣 습 니 다. 중복 이 좋 습 니 다. 선급.
5. 숫자 를 옮 겨 다 니 면 스 택 에 눌 러 넣 기
6. 요소 스 택 에 두 개의 연산 자 만 있 고 스 택 의 맨 위 요 소 는 연산 자 를 표시 하 며 표현 식 의 값 이 끝 납 니 다.
#include
#include
using namespace std;
char str[220];//
int mat[][5]={// , mat[i][j]==1， i j ，
// + - * / 1 2 3 4 ， 0
1,0,0,0,0,
1,0,0,0,0,
1,0,0,0,0,
1,1,1,0,0,
1,1,1,0,0,
};
stack op;//
stack shuzi;//
void getop(bool &next,int &zhi,int &i)// ，next true ，
{// false， ，zhi ，i
if (i==0&&op.empty()==true)
{// ， ，
next=true;
zhi=0;
// printf("%d %d
",zhi,i);
return;
}
if (str[i]==0)
{// ， ，
next=true;
zhi=0;
// printf("%d %d
",zhi,i);
return;
}
if(str[i]>='0'&&str[i]<='9')
{// ， ，
next=false;
}
else//
{
next=true;
if (str[i]=='+')
{
zhi=1;
}
else if(str[i]=='-')
{
zhi=2;
}
else if(str[i]=='*')
{
zhi=3;
}
else if(str[i]=='/')
{
zhi=4;
}
i+=2;//i ，
// printf("%d %d
",zhi,i);
return;
}
zhi=0;//
for(;str[i]!=' '&&str[i]!=0;i++)
{// ， ， ，
zhi*=10;
zhi+=str[i]-'0';
}
if (str[i]==' ')
i++;//
// printf("%d %d
",zhi,i);
return;
}
int main()
{
while(gets(str))//
{
if(str[0]=='0'&&str[1]==0) break;// 0，
bool next1;int num; int idx=0;
while(!op.empty()) op.pop();
while(!shuzi.empty()) shuzi.pop();//
while(true)
{//
getop(next1,num,idx);//
if(next1==false)
{// ，
shuzi.push((double) num);
// printf("%d
",num);
}
else
{//
double temp;
if (op.empty()==true||mat[num][op.top()]==1)
{// ，
op.push(num);
// printf("%d
",num);
}
else//
{
while(mat[num][op.top()]==0)
{// ，
int ret=op.top();
op.pop();
double b=shuzi.top();
shuzi.pop();
double a=shuzi.top();
shuzi.pop();// ， a b
if(ret==1) temp=a+b;
else if (ret==2) temp=a-b;
else if (ret==3) temp=a*b;
else if (ret==4) temp=a/b;
shuzi.push(temp);// ，
// printf("%d
",temp);
}
op.push(num);
// printf("%d
",num);
}
}
if(op.size()==2&&op.top()==0) break;// ， ，
}
printf("%.2f
",shuzi.top());
}
return 0;
} 좋은 웹페이지 즐겨찾기
