By yusijia

Updated:

Contents
  1. 1. v1.0
  2. 2. v2.0
  3. 3. java版

v1.0

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
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

//判断是否是数字
bool isNumber(char x) {
    if (x >= '0' && x <= '9')
        return true;
    return false;
}

//判断是否为运算符
bool isOperate(char opt)
{
    // 支持的操作符
    if(opt=='+' ||
       opt=='-' ||
       opt=='*' ||
       opt=='/' ||
       opt=='(' ||
       opt==')' ||
       opt=='#')
        return true;
    else
        return false;
}

// 判断运算符优先级的函数
int priority(char x) {
    if (x == '+' || x == '-')
        return 0;
    else if (x == '*' || x == '/')
        return 1;
    else if (x == '(' || x == ')')
        return -1;
    else if (x == '#')
        return -2;
}

// 实现计算
int toCalculate(int x, char opt, int y)
{
    switch(opt){
        case '+':   return x+y;
        case '-':   return x-y;
        case '*':   return x*y;
        case '/':   return x/y;
    }
}

int calculate(string str)
{
    str += '#';//加一个结尾标志
    stack<int> number;
    stack<char> operators;
    //入符号栈的第一个字符是'#'
    operators.push('#');
    char top;

    for(unsigned int i = 0; i < str.size(); i++){
        //将数字转换成字符串并入数字栈
        if(isNumber(str[i])){
            int data = 0;
            string temp;
            temp += str[i];
            while(isNumber(str[++i])){//注意这里，如果str[i]不是数字,可以从下一个if判断操作符不需要另外i++了
                temp += str[i];
            }
            for(unsigned int j = 0; j < temp.size(); j++){
                data = data*10 + (temp[j] - '0');
            }
            //cout << "data: " << data << endl;
            number.push(data);
        }
        if(!isNumber(str[i]) && isOperate(str[i])){

            top = operators.top();
            //入栈高优先级的运算符
            if (priority(str[i]) > priority(top) || str[i] == '(') {
                operators.push(str[i]);
            }else{//将优先级高的运算符实现计算
                while (priority(str[i]) <= priority(top)) {
                    if(top == '#' && str[i] == '#'){
                        //cout << number.top() << endl;
                        return number.top();
                    }else if(top == '(' && str[i] == ')'){//当左右括号相遇时，跳过右括号，删除左括号
                        ++i;
                    }else{
                        int a = number.top(); number.pop();
                        int b = number.top(); number.pop();
                        number.push(toCalculate(b, top, a));
                    }
                    operators.pop();
                    top = operators.top();
                }
                operators.push(str[i]);//用于当top=='#'时，将最后一个运算符入栈
            }

        }

    }

}

int main()
{
    string str;
    cin >> str;
    cout << calculate(str);
    return 0;
}

v2.0

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
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

//判断是否是数字
bool isNumber(char x) {
    if (x >= '0' && x <= '9')
        return true;
    return false;
}

//判断是否为运算符
bool isOperate(char opt)
{
    // 支持的操作符
    if(opt=='+' ||
       opt=='-' ||
       opt=='*' ||
       opt=='/' ||
       opt=='(' ||
       opt==')' ||
       opt=='#')
        return true;
    else
        return false;
}

// 判断运算符优先级的函数
int priority(char x) {
    if (x == '+' || x == '-')
        return 0;
    else if (x == '*' || x == '/')
        return 1;
    else if (x == '(' || x == ')')
        return -1;
    else if (x == '#')
        return -2;
}

// 实现计算
int toCalculate(int x, char opt, int y)
{
    switch(opt){
        case '+':   return x+y;
        case '-':   return x-y;
        case '*':   return x*y;
        case '/':   return x/y;
    }
}

char compare(char a, char b)
{
    if(priority(a) > priority(b))
        return '>';
    else if(priority(a) < priority(b))
        return '<';
    return '=';
}

int calculate(string str)
{
    str += '#';//加一个结尾标志
    stack<int> number;
    stack<char> operators;
    //入符号栈的第一个字符是'#'
    operators.push('#');
    char top;

    for(unsigned int i = 0; i < str.size(); i++){
        //将数字转换成字符串并入数字栈
        if(isNumber(str[i])){
            int data = 0;
            string temp;
            temp += str[i];
            while(isNumber(str[++i])){//注意这里，如果str[i]不是数字,可以从下一个if判断操作符不需要另外i++了
                temp += str[i];
            }
            for(unsigned int j = 0; j < temp.size(); j++){
                data = data*10 + (temp[j] - '0');
            }
            number.push(data);
        }
        if(!isNumber(str[i]) && isOperate(str[i])){
            top = operators.top();
            //括号优先入栈
            if(str[i] == '('){
                operators.push(str[i]);
                continue;
            }
            switch(compare(top, str[i])){
                //入栈高优先级的运算符
                case '<' : operators.push(str[i]); break;
                //将优先级高的运算符实现计算
                case '>' :
                case '=' :
                    while(compare(top, str[i]) == '>' || compare(top, str[i]) == '='){
                        if(top == '#' && str[i] == '#')
                            return number.top();
                        else if(top == '(' && str[i] == ')')//当左右括号相遇时，跳过右括号，删除左括号
                            ++i;
                        else{
                            int a = number.top(); number.pop();
                            int b = number.top(); number.pop();
                            number.push(toCalculate(b, top, a));
                        }
                        operators.pop();
                        top = operators.top();
                    }
                    operators.push(str[i]);//用于当top=='#'时，将最后一个运算符入栈
                    break;
            }
        }
    }

}

int main()
{
    string str;
    cin >> str;
    cout << calculate(str);
    return 0;
}

java版

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
public class Test {

	//判断是否是数字
	static boolean isNumber(char x) {
	    if (x >= '0' && x <= '9')
	        return true;
	    return false;
	}
	
	//判断是否为运算符
	static boolean isOperate(char opt)
	{
	    // 支持的操作符
	    if(opt=='+' ||
	       opt=='-' ||
	       opt=='*' ||
	       opt=='/' ||
	       opt=='(' ||
	       opt==')' ||
	       opt=='#')
	        return true;
	    else
	        return false;
	}
	
	// 判断运算符优先级的函数
	static int priority(char x) {
	    if (x == '+' || x == '-')
	        return 0;
	    else if (x == '*' || x == '/')
	        return 1;
	    else if (x == '(' || x == ')')
	        return -1;
	    else if (x == '#')
	        return -2;
	    return -1024;
	}
	
	// 实现计算
	static int toCalculate(int x, char opt, int y)
	{
		int data = 0;
	    switch(opt){
	        case '+':   data = x+y; break;
	        case '-':   data = x-y; break;
	        case '*':   data = x*y; break;
	        case '/':   data = x/y; break;
	        default: break;
	    }
		return data;
	}
	
	static int calculate(String str)
	{
	    str += '#';//加一个结尾标志
	    ArrayList<Integer> number = new ArrayList<Integer>();
	    ArrayList<Character> operators = new ArrayList<Character>();
	    //入符号栈的第一个字符是'#'
	    operators.add('#'); 
	    char top;

	    for(int i = 0; i < str.length(); i++){
	        //将数字转换成字符串并入数字栈
	        if(isNumber(str.charAt(i))){
	            int data = 0;
	            String temp = "";
	            temp += str.charAt(i);
	            while(isNumber(str.charAt(++i))){//注意这里，如果str[i]不是数字,可以从下一个if判断操作符不需要另外i++了
	                temp += str.charAt(i);
	            }
	            for(int j = 0; j < temp.length(); j++){
	                data = data*10 + (temp.charAt(j) - '0');
	            }
	            number.add(data);
	        }
	        if(!isNumber(str.charAt(i)) && isOperate(str.charAt(i))){

	            top = operators.get(operators.size() - 1);
	            //入栈高优先级的运算符
	            if (priority(str.charAt(i)) > priority(top) || str.charAt(i) == '(') {
	                operators.add(str.charAt(i));
	            }else{//将优先级高的运算符实现计算
	                while (priority(str.charAt(i)) <= priority(top)) {
	                    if(top == '#' && str.charAt(i) == '#'){
	                        return number.get(number.size() - 1);
	                    }else if(top == '(' && str.charAt(i) == ')'){//当左右括号相遇时，跳过右括号，删除左括号
	                        ++i;
	                    }else{
	                        int a = number.remove(number.size() - 1);
	                        int b = number.remove(number.size() - 1);
	                        number.add(toCalculate(b, top, a));
	                    }
	                    operators.remove(operators.size() - 1);
	                    top = operators.get(operators.size() - 1);
	                }
	                operators.add(str.charAt(i));//用于当top=='#'时，将最后一个运算符入栈
	            }

	        }

	    }
		return 1024;
	}
	
	public static void main(String[] args) {
		System.out.println(calculate("12-2"));
	}
Contents
  1. 1. v1.0
  2. 2. v2.0
  3. 3. java版