Stack

栈

求解表达式的值

用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法算术表达式，计算该表达式的运算结果(保留小数点后一位).
Input (56-20)/(4+2)
Output 6.0

  • 算法思想
    1.中缀表达式转化为后缀表达式
    2.后缀表示式求值
    头文件
    1
    2
    3
    #include <iostream>
    #include <stack>
    using namespace std;

主函数中缀表达式存入数组exp

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
	char exp[100], postexp[100];
	scanf("%s", exp);
	printf("中缀表达式："); 
	printf("%s\n", exp);
	Trans(exp, postexp);
	printf("后缀表达式：");
	printf("%s\n", postexp);
	printf("表达式的值：");
	printf("%.1f\n", Disp(postexp));
	return 0;
}

1.函数Trans将中缀表达式转化为后缀表达式
定义char类型栈a，扫描字符串exp
只让运算符进栈，数字字符存入数组postexp
对于不同运算符
‘(’：进栈
‘)’：将最后进入的’(’之前的运算符出栈，并存放到postexp中，然后将’(’出栈
‘+’、’-’：出栈，运算符存放到postexp中，直到栈空或栈顶为’(’
‘*’、’/’：出栈，运算符存放到postexp中，直到栈空或栈顶为’(’、’+’、’-’

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
void Trans(char *exp, char postexp[])
{
	char e;
	stack<char> a;
	int i=0;
	while(*exp!='\0')
	{
		switch(*exp)
		{
			case '(': a.push('('); exp++; break;
			case ')': e = a.top(); 
					  a.pop();
					  while(e!='(')
					  {
					  	postexp[i++] = e;
					  	e = a.top(); a.pop();
					  }
					  exp++; break;
			case '+': 
			case '-': while(!a.empty())
					  {
					  	e = a.top();
					  	if(e!='(')
					  	{
					  		postexp[i++] = e;
					  		e = a.top(); a.pop();
						}
						else 
							break;
					  }
					  a.push(*exp); exp++; break;		  
			case '*':
			case '/': while(!a.empty())
					  {
					  	e = a.top();
					  	if(e=='*'||e=='/')
					  	{
					  		postexp[i++] = e;
					  		e = a.top();
						  }
						else
							break;
					  }
					  a.push(*exp); exp++; break;
			default :
				while(*exp>='0' && *exp<='9')    //将连续数字字符存入数组postexp 
				{
					postexp[i++] = *exp;
					*exp++;		
				}
				postexp[i++] = '#';			//连续数字字符后加'#'以标记 
		}
	}
	while(!a.empty())
	{
		e = a.top();
		a.pop();
		postexp[i++] = e;
	}
	postexp[i] = '\0';      //后缀表达式以字符串形式存放 
}

2.函数Disp计算后缀表达式的值
定义double类型栈opnd，扫描数组postexp
数字字符：转化为数值并进栈
运算符：退栈两个数，计算，将结果进栈
扫描结束，出栈结果即为表达式的值

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
double Disp(char *postexp)
{
	stack<double> opnd;
	double a, b, c, e, d;
	while(*postexp!='\0')
	{
		switch(*postexp)
		{
			case '+': a = opnd.top(); opnd.pop();
					  b = opnd.top(); opnd.pop();
					  c = a+ b;
					  opnd.push(c);
					  break;
			case '-': a = opnd.top(); opnd.pop();
					  b = opnd.top(); opnd.pop();
					  c = b-a;
					  opnd.push(c);
					  break;
			case '*': a = opnd.top(); opnd.pop();
					  b = opnd.top(); opnd.pop();
					  c = a* b;
					  opnd.push(c);
					  break;
			case '/': a = opnd.top(); opnd.pop();
					  b = opnd.top(); opnd.pop();
					  if(a)
					  {
					  	c = (double)b/a;
					  	opnd.push(c);
					  	break;
					  }
					  else exit(0);
		    default:
		    	d = 0;
		    	while(*postexp>='0' && *postexp<='9')
		    	{
		    		d=10*d+*postexp-'0';    //连续的数字字符转化为数值，
		    		postexp++;				//直到遇到'#'不再循环  
				}
				opnd.push(d);
		    	break;
		}
		postexp++;
		e = opnd.top();
	}
	e = opnd.top();
	return e;
}

————————运行结果————————

数据结构与算法
栈

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！