数据结构实验之栈三：后缀式求值（基本操作数一位正整数）

以你之姓@ 2022-06-14 11:39 53阅读 0赞

Think:  
1知识点  
1>后缀表达式求值方式：  
从左往右运算，遇到数字存到栈里，遇到运算符将栈顶两个元素弹出进行运算，运算完成将运算结果入栈；[后缀表达式——百度百科链接][Link 1]  
2>stack容器初级用法+string初级用法

[SDUT题目链接][SDUT]  
[建议可参考博客][Link 2]

数据结构实验之栈三：后缀式求值  
Time Limit: 1000MS Memory Limit: 65536KB

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

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

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

Example Input  
59\*684/-3\*+\#

Example Output  
57

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

Author

以下为Runtime Error代码——EOF无法结束？

#include <bits/stdc++.h>
    
    using namespace std;
    
    stack <int> sta;
    
    int main(){
        int l, i, x, y1, y2, y;
        string st;
        while(getline(cin, st, '#')){
            l = st.size();
            while(!sta.empty())
                sta.pop();
    
            for(i = 0; i < l; i++){
                if(st[i] >= '0' && st[i] <= '9'){
                    x = st[i] - '0';
                    sta.push(x);
                }
                else {
                    y2 = sta.top();/*后进栈*/
                    sta.pop();
                    y1 = sta.top();/*前进栈*/
                    sta.pop();
    
                    if(st[i] == '*'){
                        y = y1*y2;
                    }
                    else if(st[i] == '/'){
                        y = y1/y2;
                    }
                    else if(st[i] == '-'){
                        y = y1-y2;
                    }
                    else if(st[i] == '+'){
                        y = y1+y2;
                    }
                    sta.push(y);
                }
            }
            printf("%d\n", sta.top());
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Runtime Error
    Take time: 0ms
    Take Memory: 0KB
    Submit time: 2017-06-19 16:48:26
    ****************************************************/

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    stack <int> sta;
    
    int main(){
        int l, i, x, y1, y2, y;
        string st;
        while(getline(cin, st)){
            l = st.size();
            l -= 1;
            while(!sta.empty())
                sta.pop();
    
            for(i = 0; i < l; i++){
                if(st[i] >= '0' && st[i] <= '9'){
                    x = st[i] - '0';
                    sta.push(x);
                }
                else {
                    y2 = sta.top();/*后进栈*/
                    sta.pop();
                    y1 = sta.top();/*前进栈*/
                    sta.pop();
    
                    if(st[i] == '*'){
                        y = y1*y2;
                    }
                    else if(st[i] == '/'){
                        y = y1/y2;
                    }
                    else if(st[i] == '-'){
                        y = y1-y2;
                    }
                    else if(st[i] == '+'){
                        y = y1+y2;
                    }
                    sta.push(y);
                }
            }
            printf("%d\n", sta.top());
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 204KB
    Submit time: 2017-06-19 16:49:24
    ****************************************************/

[Link 1]: http://baike.baidu.com/link?url=NSmIyRnOXQW7Ecg4VsXKPakunbn_L-m4sXIVniVYeVpAxKsxcO1kP4D1472YSgHp6aRVr-DA9USDbsWo1YTsd4NlI2TI1pdmF84rEpxsMaEap241QuKr9pp6YfeB4TH1ciP-28-FyIV36UwZZXBZlq
[SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2133.html
[Link 2]: http://blog.csdn.net/ripwangh/article/details/46366275