java实现中缀表达式转后缀的方法

本文先给出思路与方法，最后将给出完整代码： 算法综述： 一、中缀表达式转后缀表达式： 1.中缀表达式要转后缀表达式，首先需要两个stack（栈），其中一个应用于存放字符，另一个用于存放数字。 2.读到数字直接存入数字栈中，读到字符时，要咸鱼栈内前一元素（字符）进行比较，当当前（要存入的字符）优先级大于迁移字符时才存入，否则（>=）要仿佛将栈内元素弹出，并依次存入数字栈中。 提示：‘（' 的优先级默认比所有字符都 0 Comments

本文先给出思路与方法，最后将给出完整代码：

算法综述：

一、中缀表达式转后缀表达式：

1.中缀表达式要转后缀表达式，首先需要两个stack（栈），其中一个应用于存放字符，另一个用于存放数字。

2.读到数字直接存入数字栈中，读到字符时，要咸鱼栈内前一元素（字符）进行比较，当当前（要存入的字符）优先级大于迁移字符时才存入，否则（>=）要仿佛将栈内元素弹出，并依次存入数字栈中。

提示：‘（' 的优先级默认比所有字符都小。所有字符都可以存在它后面；同时夜笔所有字符都大，可以存在所有字符后面

3.遇到 ‘）'时将栈内所有字符依次弹出，并存入数字栈中，知道遇到 ‘（' 为止

4.当所有字符、数字访问完毕时，栈内很可能还会有剩余的字符，这是将他们一次弹出，并纯如数字栈中

小技巧：

1.存放‘+'，‘-'时，如果只有当前一个数位空或者‘（' 时才进行存入操作，否则均弹出。

2.存放 ‘*'，‘/' 时，只有当前一个数位 ‘*'，‘/' 时才弹出其他情况下，均存入。

附上代码：

?

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

/*

* 中缀转后缀

*/

public void topostfix() {

// todo auto-generated method stub

int sum = 0 ;//用于记入”（）“总个数

int j = 0 ;//用于读到”）“时循环出栈

string outstack = null;

charnum.push(null);

for( int i = 0 ; i < calculatelength ; i ++){

if ( calculate[i].equals("(")) {

charnum.push(calculate[i]);

sum ++ ;

}else if ( calculate[i].equals(")") ) {

outstack = charnum.pop();//进入前先出一个

while ( !outstack.equals("(") ){

num.push(outstack);

outstack = charnum.pop();

}//最后一次outstack正好接到”（“不入栈

sum ++ ;

}else if (calculate[i].equals("*")) {

outstack = charnum.pop();

charnum.push(outstack);

while( ( outstack == "*" || outstack == "/" ) && !(outstack == null) ){

num.push(outstack);

charnum.pop();//由于前第三行又将outstack存入栈中，座椅此处再次弹出

outstack = charnum.pop();

charnum.push(outstack);

}

charnum.push("*");

}else if (calculate[i].equals("/")) {

outstack = charnum.pop();

charnum.push(outstack);

while( ( outstack == "*" || outstack == "/" ) && !(outstack == null) ){

num.push(outstack);

charnum.pop();//由于前第三行又将outstack存入栈中，座椅此处再次弹出

outstack = charnum.pop();

charnum.push(outstack);

}

charnum.push("/");

}else if (calculate[i].equals("+")) {

outstack = charnum.pop();

charnum.push(outstack);

while( !(outstack=="(") && !(outstack == null) ){

num.push(outstack);

charnum.pop();

outstack = charnum.pop();

charnum.push(outstack);

}

charnum.push("+");

}else if (calculate[i].equals("-")) {

outstack = charnum.pop();

charnum.push(outstack);

while( !(outstack=="(") && !(outstack == null) ){

num.push(outstack);

charnum.pop();

outstack = charnum.pop();

charnum.push(outstack);

}

charnum.push("-");

}else {

num.push(calculate[i]);

}

}

outstack = charnum.pop();

while ( outstack != null ) {

num.push(outstack);

outstack = charnum.pop();

}

calculatelength = calculatelength - sum ;

stack<string> zanshi = new stack<>();

for(int i = 0 ; i < calculatelength ; i ++ ){

zanshi.push(num.pop());

}

calculatetozero();

for(int i = 0 ; i < calculatelength ;i ++ ){

calculate[i] = zanshi.pop();

}

}

二、后缀表达式计算

后缀表达式计算只遵循一个原则：

首先将表达式存在栈中

遇到符号时弹出两个相应的数字，进行计算后再次 存入栈内

最后栈内身下的唯一一个数，就是所要求的结果

?

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

/*

* 后缀表达式求值

*/

public string postfix() {

int a = 0 , b = 0;//栈中弹出的两数

int sum ;//求两数运算

for (int i = 0; i < calculatelength ; i++ ) {

if (i == 0) {

num.push(calculate[i]);

}else if (calculate[i].equals("+") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a + b ;

num.push(string.valueof(sum));

}else if (calculate[i].equals("-") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a - b ;

num.push(string.valueof(sum));

}else if (calculate[i].equals("*") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a * b ;

num.push(string.valueof(sum));

}else if (calculate[i].equals("/") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a / b ;

num.push(string.valueof(sum));

}else if (calculate[i].equals("%") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a / b ;

num.push(string.valueof(sum));

}else {

num.push(calculate[i]);

}

}

return num.pop();

}

}

最后附上完整代码

//注：代码中有很多输出 方便读者实时查看运算过程中 各内容

// 这些输出导致篇幅较长 大家看明白后 删去即可

?

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

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

public class text {

stack<string> num = new stack<>(); //后缀用栈 中转后数字栈

stack<string> charnum = new stack<>();//中转后字符栈

string []calculate = new string[1000];//存字符串数组

int calculatelength = 0 ;//字符串数组长度

public text() {

// todo auto-generated constructor stub

}

//转字符串数组

public void tostringarray(string input) {

char chararray[] = input.tochararray();

int number = 0;//用于导入多位数

int j = 0 ;//用于计入当前字符串数组的位数

system.out.println(chararray.length);

for(int i = 0 ; i < chararray.length ; i++){

if(chararray[i] == '('){

calculate[j++] = "(";

}else if(chararray[i] == ')'){

calculate[j++] = ")";

}else if (chararray[i] == '+') {

calculate[j++] = "+";

}else if (chararray[i] == '-') {

calculate[j++] = "-";

}else if (chararray[i] == '*') {

calculate[j++] = "*";

}else if (chararray[i] == '/') {

calculate[j++] = "/";

}else if (chararray[i] == '%') {

calculate[j++] = "%";

}else if (chararray[i] == '#') {

calculate[j++] = "#";

}else {

string str=string.valueof(chararray[i]);

number = number * 10 + integer.parseint(str);system.out.println("123");

if( (i + 1) == chararray.length || chararray[i+1] < '0' || chararray[i+1] > '9'){

if ( (i + 1) != chararray.length && chararray[i+1] == ' ') {

system.out.println("456");i++;

}

calculate[j++] = string.valueof(number);

system.out.println(number);

number = 0 ;

}

}

system.out.println("---z->" + calculate[i]);

}

calculatelength = j-- ;//不--会将‘#'存入

}

public void outputcalculate() {

for(int i = 0 ; i < calculatelength ; i ++ ){

system.out.println(calculate[i]);

}

}

public void calculatetozero() {

for(int i = 0 ; i < calculatelength ; i ++ ){

calculate[i]= calculate[999] ;

}

}

//中缀转后缀

public void topostfix() {

// todo auto-generated method stub

system.out.println("789");

int sum = 0 ;//用于记入”（）“总个数

int j = 0 ;//用于读到”）“时循环出栈

string outstack = null;

charnum.push(null);

system.out.println(calculatelength);

for( int i = 0 ; i < calculatelength ; i ++){

system.out.println(calculate[i]);//-----------------------------

if ( calculate[i].equals("(")) {

charnum.push(calculate[i]);

system.out.println("1-1 charpush " + calculate[i]);//-----------------------------

sum ++ ;

}else if ( calculate[i].equals(")") ) {

system.out.println("2-1 charpush " + calculate[i]);//-----------------------------

outstack = charnum.pop();//进入前先出一个

system.out.println("2-1 charpush " + outstack);//-----------------------------

while ( !outstack.equals("(") ){

system.out.println("2-2 charpush " + outstack);//-----------------------------

num.push(outstack);

outstack = charnum.pop();

}//最后一次outstack正好接到”（“不入栈

system.out.println("qiangxing 1 = " + outstack );

// outstack = charnum.pop();

system.out.println("qiangxing 2 = " + outstack );

sum ++ ;

}else if (calculate[i].equals("*")) {

outstack = charnum.pop();

charnum.push(outstack);

system.out.println("3-2 charpush " + outstack);//-----------------------------

while( ( outstack == "*" || outstack == "/" ) && !(outstack == null) ){

system.out.println("3-1 charpush " + outstack);//-----------------------------

num.push(outstack);

charnum.pop();//由于前第三行又将outstack存入栈中，座椅此处再次弹出

outstack = charnum.pop();

charnum.push(outstack);

}

system.out.println("3-3 charpush " + outstack);//-----------------------------

charnum.push("*");

}else if (calculate[i].equals("/")) {

system.out.println("5-1-0 charpush " + "1-1-1-1-1-1-1-1");//-----------------------------

outstack = charnum.pop();

system.out.println("5-1-1 charpush " + "2-2-2-2-2-2-22-2");//-----------------------------

charnum.push(outstack);

system.out.println("4-1 charpush " + outstack);//-----------------------------

while( ( outstack == "*" || outstack == "/" ) && !(outstack == null) ){

system.out.println("4-2 charpush " + outstack);//-----------------------------

num.push(outstack);

charnum.pop();//由于前第三行又将outstack存入栈中，座椅此处再次弹出

outstack = charnum.pop();

charnum.push(outstack);

}

system.out.println("4-3 charpush " + outstack);//-----------------------------

system.out.println("5-1-2 charpush " + outstack);//-----------------------------

charnum.push("/");

}else if (calculate[i].equals("+")) {

outstack = charnum.pop();

charnum.push(outstack);

system.out.println("5-1 charpush " + outstack);//-----------------------------

while( !(outstack=="(") && !(outstack == null) ){

system.out.println("5-2 charpush " + outstack);//-----------------------------

num.push(outstack);

charnum.pop();

outstack = charnum.pop();

charnum.push(outstack);

}

system.out.println("5-3 charpush " + outstack);//-----------------------------

charnum.push("+");

}else if (calculate[i].equals("-")) {

outstack = charnum.pop();

charnum.push(outstack);

system.out.println("6-1 charpush " + outstack);//-----------------------------

while( !(outstack=="(") && !(outstack == null) ){

system.out.println("6-2 charpush " + outstack);//-----------------------------

num.push(outstack);

charnum.pop();

outstack = charnum.pop();

charnum.push(outstack);

}

system.out.println("6-3 charpush " + outstack);//-----------------------------

charnum.push("-");

}else {

system.out.println("7-7 " + calculate[i]);

num.push(calculate[i]);

}

}

system.out.println("匹配结束" + outstack);

outstack = charnum.pop();

system.out.println("finish 1 == " + outstack);

while ( outstack != null ) {

num.push(outstack);

outstack = charnum.pop();

system.out.println("finish 2 == " + outstack);

}

calculatelength = calculatelength - sum ;

system.out.println( "0.0.0.0 charpush " );//-----------------------------

system.out.println("sum = " + sum + " calculate = " +

calculatelength + "calculatelength-sum = " + (calculatelength-sum));

system.out.println("over ~~~~~0 ");

stack<string> zanshi = new stack<>();

// num.pop();

for(int i = 0 ; i < calculatelength ; i ++ ){

zanshi.push(num.pop());

// system.out.println(num.pop());

}

calculatetozero();

system.out.println("over ~~~~~1 ");

for(int i = 0 ; i < calculatelength ;i ++ ){

calculate[i] = zanshi.pop();

}

system.out.println("over ~~~~~2 ");

for(int i = 0 ; i < calculatelength ;i ++ ){

system.out.println(calculate[i]);

}

system.out.println("over ~~~~~3 ");

// num.push("#");

}

//后缀计算

public string postfix() {

int a = 0 , b = 0;//栈中弹出的两数

int sum ;//求两数运算

for (int i = 0; i < calculatelength ; i++ ) {

// system.out.println("目前符号：" + calculate[i]);

if (i == 0) {

num.push(calculate[i]);

}else if (calculate[i].equals("+") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a + b ;

num.push(string.valueof(sum));

}else if (calculate[i].equals("-") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a - b ;

num.push(string.valueof(sum));

}else if (calculate[i].equals("*") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a * b ;

num.push(string.valueof(sum));

}else if (calculate[i].equals("/") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a / b ;

num.push(string.valueof(sum));

}else if (calculate[i].equals("%") ) {

b = integer.parseint(num.pop());

a = integer.parseint(num.pop());

sum = a / b ;

num.push(string.valueof(sum));

}else {

num.push(calculate[i]);

}

}

return num.pop();

}

}

结果如下：

一、前缀转后缀并输出

其中over前为转化后的后缀表达式

over后为计算结果

?

1

2

3

4

5

6

7

8

9

public class main {

public static void main(string[] args) {

text text = new text();

text.tostringarray("1+2*(3-1+2)-3");

text.outputcalculate();

text.topostfix();

system.out.println(text.postfix());

}

}

二、后缀直接输出

注意后缀表达式时

为了实现多位数运算，连续输入一串数时 ，输入完一个数加空格

如：要计算："1+2*(3-1+2)-3" 则输入："1 2 3 1-2+*+3-"

例：

?

1

2

3

4

5

6

7

8

public class main {

public static void main(string[] args) {

text text = new text();

text.tostringarray("1 2 3 1-2+*+3-");

text.outputcalculate();

system.out.println(text.postfix());

}

}

输出结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。

原文链接：https://blog.csdn.net/qq_43377749/article/details/84483862

本文链接：https://my.lmcjl.com/post/9266.html

展开阅读全文

相关文章

4 评论

留下您的评论.