算法训练 表达式计算

Posted on | In |

表达式计算

问题描述

　　输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。

输入格式
　　输入一行，包含一个表达式。

输出格式
　　输出这个表达式的值。

样例输入

1-2+3*(4-5)

样例输出

-4

数据规模和约定
　　表达式长度不超过100，表达式运算合法且运算过程都在int内进行。

1
2
3
4
5
6
7
8
9
10
从中缀表达式中从左往右依次取出数据
如遇到操作数，直接输出到后缀的队列里。
如果遇到操作符（包括括号），这里再定义一个存放操作符的栈，则:
i.如果操作符是'(',入栈
ii.如果操作符是')',则把栈里的操作符依次出栈并插入到后缀序列后面，直到遇到')'.
iii.如果操作符不是‘(’和‘)’,则：
     (1). 如果操作符的优先级比top的优先级高，则入栈
     (2).如果操作符优先级等于或小于top优先级，则将top出栈并插入到后缀序列后面，pop后,再比较栈顶元素的优先级，重复iii，直到把此操作符      插入，将此操作符入栈。
如果中序队列里的数据已经读取完毕，记录操作符的栈里，还有操作符的话，依次出栈插入到后缀序列的后面。
此时中缀就已经转换为后缀表达式,如下图

image

参考博客
https://blog.csdn.net/dream_1996/article/details/78126839

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;
#define MAX 200+2
string ch;
stack<char> s1,s2;//s1 运算符栈 
//s2 操作数 栈 
stack<int> s3;
int pri(char a){
	switch(a){
	
		case '-':
		case '+': return 1;
		case '*':
		case '/': return 2;
	}
}
bool isop(char t){
	return t=='+'||t=='-'||t=='*'||t=='/';
}
string transform(string s,int &k){
	int i=0;
	while(i<s.length()){
			if(s[i]>='0'&&s[i]<='9'){
				if((i+1<s.length()&&(s[i+1]<'0'||s[i+1]>'9'))||i==s.length()-1){
					
					s2.push(s[i]);	
					s2.push('#');						
				}			
				else {
					s2.push(s[i]);
				}
			}
			else if(isop(s[i])){
				if(s1.empty()||pri(s[i])>pri(s1.top()))
				{
					s1.push(s[i]);
					//!
				
				}
				else {
					while(!s1.empty()&&pri(s[i])<=pri(s1.top())&&s1.top()!='('){
						s2.push(s1.top());
						s1.pop();
					}
					s1.push(s[i]);
				}
			}
			else if(s[i]=='(')
				s1.push(s[i]);
			else if(s[i]==')'){
				while(!s1.empty()){
					char t=s1.top();
					if(t=='(') break;
					s2.push(t);
					s1.pop();
					
				}
				s1.pop();
			}
			
			i++;
	}
	while(!s1.empty()){
		
		s2.push(s1.top());
		s1.pop();
	
	}
	char ss[200];
	
	while(!s2.empty()){
	//!!
	ss[k++]=s2.top();
	
	s2.pop();
	}
	ss[k]='\0';
//!!
	reverse(ss,ss+k);
	
	return ss;
	
}
int val(char t,int t1,int t2){
	if(t=='+') return t1+t2;
	else if(t=='-') return t1-t2;
	else if(t=='*') return t1*t2;
	else if(t=='/') return t1/t2;
	else return 0; 
	
	
}
int cal(string ss,int k){
	char num[200];
	int len=0;
	for(int i=0;i<k;i++){
	char t=ss[i];
		if(t>='0'&&t<='9'){
		
			if(ss[i+1]=='#'){
				num[len++]=t;
				int tmp=0;
			for(int j=0;j<len;j++){
			tmp+=(num[j]-'0')*pow(10,len-1-j);
			}
		//	cout<<tmp<<endl;
			s3.push(tmp);	
			//!!
			len=0;
			tmp=0;
		}
		else num[len++]=t;
	}
		else if(t=='#') continue;
		else if(isop(t)){
			int t1=s3.top();
			s3.pop();
			int t2=s3.top();
			s3.pop();
			//!!
			int ans=val(t,t2,t1);
			s3.push(ans);
		}
		
	}
	return s3.top();
	}
	




int main(){
	getline(cin,ch);
int k;
string  ss;
ss=transform(ch,k);
//cout<<ss<<endl;
	cout<<cal(ss,k)<<endl;
	
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//表达式转换
#include<bits/stdc++.h>
using namespace std;
struct node{
	char op;
	int num;
	bool f;
};
queue<node> que;//后缀表达式序列
stack<node> s;//操作符栈 
map<char,int>op;
int main(){
	string str;
	freopen("21.txt","r",stdin);
	op['+']=op['-']=1;
	op['*']=op['/']=2;	
	op['(']=-1;	
	getline(cin,str);
	node tmp;
	//2+3*7-4
	for(int i=0;i<str.length();){
		if(str[i]>='0'&&str[i]<='9'){
			tmp.f=true;
			tmp.num=str[i]-'0';			
			while(i+1<str.length()&&str[i+1]>='0'&&str[i+1]<='9'){
				tmp.num=tmp.num*10+str[i+1]-'0';
				i++;
			}
			que.push(tmp);
			i++;
		}
			else  if(str[i]==')'){
				while(!s.empty()&&s.top().op!='('){
					que.push(s.top());
					s.pop();
				}
				s.pop();
				i++;
			
			}
			else if(str[i]=='('){
				tmp.f=false;
				tmp.op='(';
				s.push(tmp);	i++;
			}
			else{
				tmp.f=false;
				while(!s.empty()&&op[str[i]]<=op[s.top().op]){
					que.push(s.top());
					s.pop(); 
					
				}						
				tmp.op=str[i];
				s.push(tmp);
				i++;
					
				}
	  }
	while(!s.empty()){
		que.push(s.top());
		s.pop();	
	}
	while(!que.empty()){
	node tmp=que.front();
	que.pop(); 
	if(tmp.f==false)
	cout<<tmp.op<<" ";
	else{
			cout<<tmp.num<<" ";
	}
	}
	return 0;
		
}

`