표현 식 값 구하 기 (남양 이 공 - 35)

4220 단어 데이터 구조
표현 식 값 구하 기
시간 제한:
3000 ms  |  메모리 제한:
65535 KB
난이도:
4
            
설명:
ACM 팀 의 md 는 계산 기 를 만 들 고 싶 습 니 다. 그러나 그 가 하려 는 것 은 A + B 를 계산 하 는 계산기 만 이 아 닙 니 다. 그 는 표현 식 을 마음대로 입력 해도 그 값 을 구 할 수 있 는 계산 기 를 실현 하고 싶 습 니 다. 지금 은 그 가 이 계산 기 를 실현 하도록 도와 주세요.예 를 들 어 입력: "1 + 2 / 4 =" 을 입력 하면 프로그램 은 1.50 을 출력 합 니 다. (결 과 는 두 개의 소수 유지)
입력
첫 번 째 줄 에 정수 n 을 입력 하 십시오. 모두 n 조 테스트 데이터 (n < 10) 가 있 습 니 다. 각 조 의 테스트 데 이 터 는 한 줄 만 있 고 길이 가 1000 을 넘 지 않 는 문자열 입 니 다. 이 연산 식 을 표시 합 니 다. 모든 연산 식 은 "=" 입 니 다.끝 입 니 다. 이 표현 식 에는 + - * / 와 작은 괄호 만 포함 되 어 있 습 니 다. 작은 괄호 는 끼 워 넣 어서 사용 할 수 있 습 니 다. 데 이 터 는 입력 한 동작 수 에 마이너스 가 나타 나 지 않 습 니 다. 데이터 보증 나 누 기 는 0 이 되 지 않 습 니 다.
출력
각 조 는 이 조 의 연산 식 연산 결 과 를 출력 하고 출력 결 과 는 두 개의 소 수 를 유지한다.
샘플 입력
2
1.000+2/4=
((1+2)*5+1)/4=

샘플 출력
1.50
4.00

(1) 제목 링크: 남양 이 공 23
문제 풀이 방향:
접미사 표현 식 접미사 표현 식: 우선 더하기, 빼 기, 곱 하기, 제 연산 자 를 우선 순위 로 나 누고 괄호 는 최고 우선 순위 이 며, 그 다음 에 곱 하기, 빼 기, 등 호 는 최저 우선 순위 이 며, 스 택 을 이용 하여 연산 자 리 를 특정 규칙 으로 변환 하 는 데 편리 합 니 다. 그 다음 에 문자열 을 반복 합 니 다. 숫자 문자 나 소수점 연산 자 라면 접미사 표현 으로 추가 합 니 다.식, 뒤에 빈 칸 을 추가 하면 sstreamstring 흐름 입력 이 편리 합 니 다. 연산 자 문자 라면 규칙 에 따라 스 택 에 들 어가 거나 스 택 에 들 어가 면 연산 자 를 스 택 꼭대기 에 누 르 고 스 택 에서 나 오 면 연산 자 를 접미사 표현 식 에 추가 한 다음 에 빈 칸 을 추가 합 니 다.
연산 자 규칙: 먼저 스 택 이 비어 있 을 때 연산 자 를 스 택 에 넣 고 그 다음 에 연산 자 를 만 났 을 때 스 택 꼭대기 연산 자 와 비교 합 니 다. 현재 연산 자 우선 순위 가 스 택 꼭대기 연산 자 보다 높 으 면 현재 요 소 를 스 택 에 넣 습 니 다. 현재 요소 우선 순위 가 스 택 꼭대기 요소 보다 낮 으 면 스 택 에서 더 낮은 우선 순위 나 스 택 이 비어 있 을 때 까지 스 택 에서 계속 나 가 고 마지막 으로 이 연산 자 를 스 택 에 넣 습 니 다.다른: 괄호 연산 자 라면 왼쪽 괄호 를 만나면 스 택 에 들 어가 고 오른쪽 괄호 를 만나면 스 택 에서 왼쪽 괄호 와 왼쪽 괄호 이상 의 모든 연산 자 를 만 나 고 오른쪽 괄호 는 스 택 에 들 어가 지 않 습 니 다.
접미사 표현 식 값 구하 기: 위 절 차 를 통 해 접미사 표현 식 문자열 을 얻 을 수 있 으 며, 모든 숫자 문자열 과 연산 자 문 자 는 빈 칸 으로 분할 되 어 있 습 니 다. streamstring 으로 조작 할 수 있 도록 한 다음 접미사 문자열 을 옮 겨 다 니 며, 디지털 문자열 에 대해 서 는 아 토 프 () 를 사용 합 니 다.함 수 는 이 를 숫자 로 바 꾸 고 동시에 창고 에 들 어 갈 수 있 습 니 다. 만약 에 연산 자 를 만나면 창고 꼭대기 요 소 를 상응하는 연산 을 하고 마지막 에 결 과 를 창고 에 들 어 갑 니 다. 마지막 에 등호 연산 자가 끝나 면 현재 창고 의 유일한 창고 꼭대기 요 소 는 표현 식 의 값 입 니 다.
AC 코드:
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int Judge(char ch){
	//           
	if(ch == '+') return 1;
	if(ch == '-') return 1;
	if(ch == '*') return 2;
	if(ch == '/') return 2;
	if(ch == '(') return 0;
	if(ch == ')') return 0;
}
int main (void){
	string str;
	string s;
	int count ;
	cin>>count;
	while(count--){
		int i=0 ;
		str.clear();
		s.clear() ;
		cin>>str;
		stackmid; //     ,              
		stackans;//    ,          
		while(str[i] != '=')
		{
			if(str[i] == '('){//  ,      
				mid.push(str[i]);
				i++;
			}
			else if( str[i] == ')')//                     
			{
				while(mid.top()!='(')
				{
					s = s + mid.top() ;
					s += ' ';
					mid.pop() ;
				}
				mid.pop() ;
				i++;
			}
			else if(isdigit(str[i]))//                 
			{
				while(str[i]<='9'&&str[i]>='0' || str[i] =='.')
				{
					s = s + str[i];
					i++;
				}
				s += ' ';
			}
			else if(str[i] == '+'||str[i] == '-'||str[i] == '*'||str[i] == '/'){
				while(!mid.empty() && Judge(mid.top()) >= Judge(str[i])){
				//                ,       
					s = s + mid.top();
					s = s + ' ';
					mid.pop();
				}
				mid.push(str[i]);//         
				i++;
				
			}	
		}
		while(!mid.empty())//           
		{
			s = s + mid.top() ;
			s = s + ' ';
			mid.pop() ;
		}
		string temp;
		stringstream ss(s);
		char a[1000];
		double num;
		while(ss>>temp)
		{
			if( isdigit(temp[0]) ){
				for(i=0;i

좋은 웹페이지 즐겨찾기