[NowCoder] 四则运算

[frdmu]

描述
输入一个表达式（用字符串表示），求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

输入描述：

输入一个算术表达式

输出描述：

得到计算结果

示例1
输入：

3+2*{1+2*[-4/(8-6)+7]}

复制
输出：

25

 

解法：
双栈，一个符号栈，一个数字栈。
难点：如何判断‘+’ ‘-’表示正负还是加减。 解决办法：数字和符号交替出现。
代码如下：

#include <iostream>
#include <map>
#include <cstring>
#include <stack>
using namespace std;

void doCal(stack<int>& sn, stack<char>& so) {
    char op = so.top();
    so.pop();
    
    int n2 = sn.top();
    sn.pop();
    int n1 = sn.top();
    sn.pop();
    if (op == '+') sn.push(n1 + n2);
    if (op == '-') sn.push(n1 - n2);
    if (op == '*') sn.push(n1 * n2);
    if (op == '/') sn.push(n1 / n2);
}
int main() {
    map<char, int> mp = {{'(', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string s;
    
    while (getline(cin, s)) {
        stack<int> sn;
        stack<char> so;
        so.push('(');
        s += ")";
        bool isnumber = true;
        int n = s.size();
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                so.push('(');
            } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
                while (so.top() != '(') doCal(sn, so);
                so.pop();
            } else if (isnumber) {
                int start = i;
                if (s[i] == '+' || s[i] == '-') i++;
                while (i < n && isdigit(s[i])) i++;
                sn.push(stoi(s.substr(start, i-start)));
                i--;
                isnumber = false;
            } else {
                while (mp[s[i]] <= mp[so.top()]) doCal(sn, so);
                so.push(s[i]);
                isnumber = true;
            }
        }
        
        cout << sn.top() << endl;
    }
    
    return 0;
}

Refer:
四则运算