题解 | #表达式求值#

表达式求值

http://www.nowcoder.com/practice/9566499a2e1546c0a257e885dfdbf30d

思路:

  1. 将表达式转为逆波兰式;
  2. 计算逆波兰式的值。
    PS:默认表达式中不含空格。
#include <iostream>
#include <string>
#include <stack>
using namespace std;

// 通过一个单调栈(存储操作符)将表达式转为逆波兰式
string trans(string exp) {
    stack<char> opt_stk;
    int idx = 0, len = exp.length();
    string ans;
    char num_sign = '#';
    while (idx < len) {
        switch (exp[idx]) {
            case '(':
                opt_stk.push('(');
                idx++;
                break;
            case ')':
                while (opt_stk.top() != '(') {
                    ans += opt_stk.top();
                    opt_stk.pop();
                }
                opt_stk.pop();
                idx++;
                break;
            case '+':
            case '-':
                // 以下两种情况将负号视作符号位,不将其入栈
                // 1. 负号在第一位
                // 2. 负号前一位字符不是数字,也不是反括号
                if (exp[idx] == '-' && (idx == 0 || (idx > 0 && exp[idx-1] != ')' && !isdigit(exp[idx-1])))) {
                    num_sign = '@';
                    idx++;    
                } else {
                    while (!opt_stk.empty() && opt_stk.top() != '(') {
                    ans += opt_stk.top();
                    opt_stk.pop();
                    }
                    opt_stk.push(exp[idx++]);
                }
                break;
            case '*':
            case '/':
                while (!opt_stk.empty()) {
                    char c = opt_stk.top();
                    if (c == '*' || c == '/') {
                        ans += c;
                        opt_stk.pop();
                    } else 
                        break;
                }
                opt_stk.push(exp[idx++]);
                break;
            default:
                while (idx < len && exp[idx] <= '9' && exp[idx] >= '0') 
                    ans += exp[idx++];
                ans += num_sign;
                if (num_sign == '@') num_sign = '#';
        }
    }
    while (!opt_stk.empty()) {
        ans += opt_stk.top();
        opt_stk.pop();
    }
    return ans;
}

// 也只用一个栈,栈中存放的是操作数
double compute_value(string exp) {
    stack<double> stk;
    int idx = 0, len = exp.length();
    while (idx < len) {
        char c = exp[idx];
        if (c == '+') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(a + b);
        } else if (c == '-') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(b - a);
        } else if (c == '*') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(a * b);
        } else if (c == '/') {
            double a = stk.top(); 
            stk.pop();
            double b = stk.top();
            stk.pop();
            stk.push(b / a);
        } else {
            double num = 0;
            while (exp[idx] <= '9' && exp[idx] >= '0') 
                num = num * 10 + exp[idx++] - '0';
            if (exp[idx] == '@') num = -num;
            stk.push(num);
        }
        idx++;
    }
    return stk.top();
}

int main() {
    string exp;
    cin >> exp;
//     cout << trans(exp) << endl;
    cout << compute_value(trans(exp));

    return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
2 收藏 评论
分享

全站热榜

正在热议