数据结构实验之栈与队列三：后缀式求值

Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description

对于一个基于二元运算符的后缀表示式（基本操作数都是一位正整数），求其代表的算术表达式的值。
Input

输入一个算术表达式的后缀式字符串，以‘#’作为结束标志。
Output

求该后缀式所对应的算术表达式的值，并输出之。
Sample Input
59*684/-3*+#

Sample Output
57

Hint

基本操作数都是一位正整数!
#include<iostream>
using namespace std;
int top = 0, stack[1001];
int main()
{
    char s[1001];
    cin>>s;
    for(int i = 0; s[i] != '#'; i++)
    {
        if(s[i] >= '1' && s[i] <= '9')
            stack[++top] = int(s[i] - '0');
        else
        {
            if(s[i] == '+')
            {
                stack[top - 1] = stack[top - 1] + stack[top];
                top--;
            }
            if(s[i] == '-')
            {
                stack[top - 1] = stack[top - 1] - stack[top];
                top--;
            }
            if(s[i] == '*')
            {
                stack[top - 1] = stack[top - 1] * stack[top];
                top--;
            }
            if(s[i] == '/')
            {
                stack[top - 1] = stack[top - 1] / stack[top];
                top--;
            }
        }
    }
    cout<<stack[top];
    return 0;
}

栈的应用-后缀式求值
什么是后缀式？
怎样求后缀式的值呢？
代码


什么是后缀式？
后缀式就是把运算符写在运算对象的后面。比如(a+b+cd)转化为后缀式为abcd++e/。注意，中缀式转化为前缀或者后缀式是不唯一的，所以后缀式可以有多种。
怎样求后缀式的值呢？
后缀式求值可以用栈来解决。当遇到数值的时候入栈，当遇到运算符的时候，连续两次出栈，将两个元素结合运算符进行运算，将结果当成新遇到的数值入栈。如此往复，直到遇到终止符号#。此时栈里只有一个元素就是表达式的值。
代码
int op(int a, char op,int b){  //本函数完成a op b，op为操作符
	if(op == '+')
		return a + b;
	if(op == '-')
		return a - b;
	if(op == '*')
		return a * b;
	if(op == '/'){
		if(b == 0){  
			cout<<ERROR<<endl;
			return 0;
		}else
		return a / b;
	}
		
}

int com(string exp){
	int stack[MAXSIZE];
	int top = -1;
	for(int i = 0; exp[i]!='#';i++){
		if(exp[i]>='0'&&exp[i]<='9')
			stack[++top] = exp[i] - '0'; //输入的是字符型，入栈的是整型 
		else{  //遇到字符
			int a = stack[top--];
			int b = stack[top--];
			char op = exp[i];
			stack[++top] = op(a ,op,b);
		}
	}
	return stack[top];
}

数据结构实验之栈与队列三：后缀式求值

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic Discuss

Problem Description
对于一个基于二元运算符的后缀表示式（基本操作数都是一位正整数），求其代表的算术表达式的值。

Input
输入一个算术表达式的后缀式字符串，以‘#’作为结束标志。

Output
求该后缀式所对应的算术表达式的值，并输出之。

Sample Input
59684/-3+#

Sample Output
57

Hint
基本操作数都是一位正整数!

Source
数字放入栈中，遇到运算符就弹出两个数字进行运算

再将结果压入栈中

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
int main()
{
    int i,a,b,sum;
    char s[101];
    gets(s);
    stack<int>q;
    int len=strlen(s);
    for(i=0;i<len-1;i++)
    {
        if(s[i]>='0'&&s[i]<='9')
        {
            q.push(s[i]-'0');//注意将字符转化为数字进栈
        }
        else
        {
            a=q.top();q.pop();
            b=q.top();q.pop();
            if(s[i]=='+')
            {
                sum=a+b;q.push(sum);
            }
            if(s[i]=='-')
            {
                sum=b-a;q.push(sum);
            }
            if(s[i]=='*')
            {
                sum=a*b;q.push(sum);
            }
            if(s[i]=='/')
            {
                sum=b/a;q.push(sum);
            }
        }
    }
    printf("%d\n",q.top());
    return 0;
}

PTA-后缀式求值
传送门
这道题是一个简单栈的使用~
给你的后缀表达式，那么我们遇到操作数就进栈，遇到操作符就弹两个出来进行运算，然后把运算出来的结果再入栈。特别注意，运算的时候是先出栈的是第二操作数，后出栈的是第一操作数。

再就是注意操作数为负数的问题~所以当我们遇到减号的时候，不能一下子就把它看成操作符，还需要判断一下。

就这两个易错点。
因为我是字符串读入的~所以要把字符串转化为浮点数，我们可以用C中的函数atof（或者C++中的函数strtod），因为这两个函数都是操作char*类型的，我是string类型的，所以需要转化一下，string的函数c_str()转化即可。
代码部分：
#include <bits/stdc++.h>
using namespace std;

string str;
int n;
stack<double> s;

int main()
{
	double num1, num2;
	getline(cin, str);
	n = str.size();
	for (int i = 0; i < n; i++)
	{
		if (str[i] == ' ')
		{
			continue;
		}
		else if ((str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') && (i == n - 1 || str[i + 1] == ' '))
		{//可能存在负数的情况 
			num1 = s.top();
			s.pop();
			num2 = s.top();
			s.pop();
			if (str[i] == '+')
			{
				s.push(num1 + num2);
			}
			else if (str[i] == '-')
			{
				s.push(num2 - num1);
			}
			else if (str[i] == '*')
			{
				s.push(num1 * num2);
			}
			else
			{
				s.push(num2 / num1);
			}
		}
		else
		{
			string temp = "";
			while (str[i] != ' ')
			{
				temp += str[i];
				i++;
			}
			num1 = atof(temp.c_str());
			s.push(num1);
		}
	}
	printf ("%.1f\n", s.top());
	s.pop();
	return 0;
}