[TOC]

题目1 : 简单计算器

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

编写一个程序可以完成基本的带括号的四则运算。其中除法(/)是整除，并且在负数除法时向0取整。(C/C++/Java默认的除法就是向0取整，python默认的是向负无穷取整。)

例如计算 100 ( 2 + 12 ) - (20 / 3) 2, 结果是1388。

输入

一个长度不超过100的字符串，代表要计算的算式。包含数字0-9以及+-*/()。

输入保证计算过程不会超过32位有符号整数，并且其中的’-‘都是减号没有负号。

输出

计算的结果。

样例输入

100*(2+12)-(20/3)*2

样例输出

1388

思路

输入的是中缀表达式，计算机计算需要将中缀表达式转换成前缀或后缀表达式，即波兰式或逆波兰式。

CODE:中缀表达式、逆波兰式、栈、队列

hiho-169.cpp
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <queue>
#include <stack>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;

string operators[4] = {"+", "-", "*", "/"}; // 四则运算符

// 比较两个操作符的优先级
int judge(string op1, string op2) {
    if(op1 == "(") return -1;
    else if(op1 == "+" || op1 == "-") {
        if(op2 == "*" || op2 == "/")  return -1;
        else return 0;
    }
    if(op1 == "*" || op1 == "/") {
        if(op2 == "+" || op2 == "-") return 1;
        else return 0;
    }
}

bool IsOperator(string str) {
    for(int i = 0; i < 4; i++) {
        if(str == operators[i])
            return true;
    }
    return false;
}

// 后缀表达式求值程序
int Calculate(queue<string> postFix) {
    stack<string> S;

    while(!postFix.empty()) {
        string tmp = postFix.front();
        if(!IsOperator(tmp)) {  // 如果是数字就进栈
            S.push(tmp);
        }
        else {
            string strA, strB;
            int intA, intB;
            int ans;
            char* end;

            strB = S.top();
            intB = static_cast<int>(strtol(strB.c_str(),&end,10));
            S.pop();
            strA = S.top();
            intA = static_cast<int>(strtol(strA.c_str(),&end,10));
            S.pop();

            if(tmp == "+") ans = intA + intB;
            else if(tmp == "-") ans = intA - intB;
            else if(tmp == "*") ans = intA * intB;
            else ans = intA / intB;

            stringstream ss;
            int t = ans;
//            cout << t << endl;
            ss << ans;
            S.push(ss.str());
            ss.str("");
        }
        postFix.pop();
    }
    cout << S.top() << endl;
    return 0;
}

// 中缀表达式转换成后缀表达式
void Infix_to_Postfix(queue<string> inFix) {
    queue<string> Q;
    stack<string> S;

    while(!inFix.empty()) {
        string  str = inFix.front();
        if(str == "(") S.push(str);
        else if(str == ")") {
            while(S.top() != "(") {
                Q.push(S.top());
                S.pop();
            }
            S.pop();
        }
        else {
            if(!IsOperator(str))
                S.push(str);
            else {
                while(!S.empty() && judge(S.top(), str) >= 0) {
                    Q.push(S.top());
                    S.pop();
                }
                S.push(str);
            }
        }
        inFix.pop();
    }

    while(!S.empty()) {
        Q.push(S.top());
        S.pop();
    }
    Calculate(Q);

//    cout << "后缀表达式：" << endl;
//    while(!Q.empty()) {
//        cout << Q.front() << " ";
//        Q.pop();
//    }
//    cout << endl;
    return ;
}

void Infix_to_Queue(char formula[]) {
    queue<string> inFix;
    int len = strlen(formula);
    string str = "";
    for(int i = 0; i < len; i++) {
        if(formula[i] > '9' || formula[i] < '0') {
            if(str != "") {
                inFix.push(str);
                str = "";
            }
            str += formula[i];
            inFix.push(str);
            str = "";
            continue;
        }
        str += formula[i];
    }
    if(str != "") inFix.push(str);

    Infix_to_Postfix(inFix);

//    while(!inFix.empty()) {
//        str = inFix.front();
//        cout << str << " ";
//        inFix.pop();
//    }
    return ;
}

int main()
{
    char formula[105];
    cin >> formula;
    Infix_to_Queue(formula);
    return 0;
}