W.T.的博客

Every day to be a little better

stack实现表达式中缀转后缀计算结果

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟
stack，queue的使用实例

1. 原文

输入样式

1
30/90-26+(97-5)*6

输出样式

1
526.33

2. 解析思路

  • 先转为后缀表达式，操作数直接转入队列中，操作符存入栈中

    当栈中优先级高于或等于栈外优先级时，出栈

    当栈中优先级低于栈外优先级时，入栈

    最终所有操作符转入队列中

  • 后缀表达式出队，转入栈中，操作数直接入栈，碰到操作符，出栈两个操作数，计算结果后入栈结果，最终栈内最后一个数即为结果

3. 代码

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
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<cctype>
using namespace std;
map<char,int> inop,outop;
struct node{
	int num;
	char oper;
	bool flag;
	node(){
		num = 0;
	}
};
queue<node> q;
stack<node> s,ans;
char str[210];
void infix(){
	for (int i = 0; str[i] != '\0';)
	{
		node temp;
		if (isdigit(str[i]))
		{
			temp.flag = true;
			for (; isdigit(str[i])&& str[i] != '\0'; ++i)
			{
				temp.num = temp.num*10+str[i]-'0';
			}
			q.push(temp);
		}else{
			temp.flag = false;
			if (str[i]=='(')
			{
				temp.oper='(';
				s.push(temp);	
			}
			else if (str[i]==')')
			{
				while(s.top().oper!='('){
					q.push(s.top());
					s.pop();
				}
				s.pop();
			}else{
				while(!s.empty()&&inop[s.top().oper]>=outop[str[i]]){
					q.push(s.top());
					s.pop();
				}
				temp.oper = str[i];
				s.push(temp);
			}
			i++;
		}
	}
	while(!s.empty()){
		q.push(s.top());
		s.pop();
	}
}
int main(){
	freopen("A0721.txt","r",stdin);
	scanf("%s",str);
	inop['('] = 1; inop['*'] = 5; inop['/'] = 5; inop['+'] =3; inop['-'] =3;  inop[')'] = 6;
	outop['(']= 6; outop['*'] =4; outop['/'] =4; outop['+'] =2; outop['-']= 2;outop[')'] = 1;
    infix();

    while(!q.empty()){
    	node top = q.front();
    	q.pop();
    	
    	if (top.flag==true)
    	{
    		//printf(" %d ",top.num);
    		ans.push(top);
    	}
    	else{
    		//printf(" %c ",top.oper);
    		int b = ans.top().num;
    		ans.pop();
    		int a = ans.top().num;
    		ans.pop();

    		node temp;
    		temp.flag = true;
    		if (top.oper == '+'){ temp.num = a+b; }
    		if (top.oper == '-'){ temp.num = a-b; }
    		if (top.oper == '*'){ temp.num = a*b; }
    		if (top.oper == '/'){ temp.num = a/b; }
    		ans.push(temp);
    	}
    }
    printf("%d\n",ans.top().num);
	return 0;
}
本文结束  感谢您的阅读