#include "stdio.h"
#include "malloc.h"
#define MAXSIZE 10
//定义一个顺序栈
typedef struct Stack {
int top;//栈顶指针
char str[MAXSIZE];
} Stack;
void initStack(Stack &stack) {
stack.top = -1;
}
void push(Stack &stack) {
stack.str[++stack.top] = '(';
}
void pop(Stack &stack, char &str) {
if (stack.top < 0) {
//没有元素可弹
return;
}
str = stack.str[stack.top--];
}
bool isLeagChar(Stack &stack, char str[]) {
//遍历字符串
int index = 0;
while (str[index] != '\0') {
char c = str[index++];
if (c == '(') {
//压栈
push(stack);
} else if (c == ')') {
//弹栈
char popStr = '0';
pop(stack, popStr);
if (popStr == '0' || popStr != '(') {
return false;
}
}
}
if(stack.top != -1){
return false;
}
return true;
}
int main() {
//定义一个Stack
Stack stack;
//初始化一个栈
initStack(stack);
char str[] = "((aa)ad)()())";
bool isChar = isLeagChar(stack, str);
printf("%d\n", isChar);
}
（（ 15 / （7-（1+1））） * 3 ） - （2+（1+1）），将某个中缀表达式转换为逆波兰表达式，如果是+ - * 运算倒是对顺序没什么有要求，但是如果是除法运算，则必须严格按照原式的除法顺序，如果是正常的加减乘，可以先写操作数，再写运算符，如果是除法，则要将操作数按原顺序写，如果是有小括号的优先级，则可以先写操作数，将操作符往右写。如上述中缀表达式转逆波兰表达式后为：(,隔开的是两个操作符)
15,7,1,1±3 2,1,1+±
中缀表达式中运算符优先级生效的顺序正好和后缀表达式运算符的从左到右的顺序是一样的（前提是使用了左优先原则），虽然中缀表达式转换成逆波兰表达式后可能有多种结果，但是如果遵循了左优先原则，那么只会有一种结果，这也就是算法强调确定性，同样的输入只能有同样输出，同时在严格遵守了原式的加减乘以后，中缀表达式转后缀表达式后，操作数的顺序也是不变的
使用栈思想解决逆波兰表达式的问题思路：
1.创建一个栈并初始化，同时获取到一个逆波兰表达式
2.遍历这个逆波兰表达式字符串，如果是数字则压栈，如果是运算符，则从栈中弹出2个元素，并使用该操作符计算这两个元素的值，计算好后再次压栈。如果整个逆波兰表达式是合法的，那么栈中最后一个元素就是整个表达式的结果。
依次遍历逆波兰表达式，如果是操作符则将操作符拼接到前两个操作数中间，再匹配一个小括号，这整个式子作为一个数，再依次遍历·····。
遍历到当前字符，是一个 - 号，然后查看栈中的栈顶元素是一个+号，则可以放心的把这个+号弹出来加入到后缀表达式中，因为当前是-号，栈顶是+号，说明-号和+号中间肯定有一个操作数，那么这个操作数既然+先入栈，则根据左优先原则，把+号弹出，此时我们能把-号加入到表达式吗？不能，因为我们无法保证-号下一个操作符是*/还是±，还是小括号，所以需要先入栈，那假设又遍历到一个运算符，如果是+，则根据左优先原则，把-之前的-弹出，如果是*/，则*/的优先级比-高，但是即使是*/，则无法保证，/后面有没有 小括号，此时依然需要先把/压入栈中，等待下一个操作符弹出。
注意：
1.栈中越先保存的运算符，说明在原式中先被运算了，此时如果当前的运算符和栈中弹出的运算符的优先级是相等的，那么应该先将栈中的运算符加入到后缀表达中。
2.如果弹出的运算符比自己的优先级更低，说明咱这两个运算符之间的这个数是例如这样的 -A* , +B/,我的优先级比你的高，理论上来说，我应该先入表达式，但是此时如果后面有小括号，则小括号里面的优先级更高了，所以此时暂时把这个运算符压入栈，等待下一个运算符。
#include "stdio.h"
#include "malloc.h"
#include package com.sci.app.ds;
public class SeqStackTest {
public static void main(String[] args) {
String str = "15/5+2*3-1";
//准备一个顺序栈
SeqStack<Character> seqStack = new SeqStack<>(str.length());
//准备一个字符串容器，存放字符序列
StringBuffer sb = new StringBuffer();
//遍历中缀表达式
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
//如果是操作数，则直接加入表达式
if (c == '+' || c == '-' || c == '*' || c == '/'){
//判断栈是否为空，如果为空，则压入栈
if (seqStack.size() == 0){
seqStack.push(c);
}else {
//如果栈不为空，则依次弹出栈顶的操作符与当前操作符相比，如果优先级高于或等于当前操作符
//则入栈，否则将当前操作符入栈
Character topElement = seqStack.getTopElement();//获取栈顶元素，注意此时只是获取，没有弹栈
boolean isTopHigher = isTopElementHigher(c,topElement);
if (isTopHigher){
//直到遇到优先级比自己低的或者栈空为止
while (isTopHigher && seqStack.size() > 0){
//弹出栈顶元素
Character pop = seqStack.pop();
sb.append(pop);
topElement = seqStack.getTopElement();
if (topElement == null){
break;
}
isTopHigher = isTopElementHigher(c,topElement);
}
seqStack.push(c);
}else {
//栈顶元素比当前操作符优先级低，此时不能将当前操作符直接压入表达式，应先压入栈，因为不知道当前操作符后是否有小括号
seqStack.push(c);
}
}
}else {
//操作数直接加入表达式
sb.append(c);
}
}
//整个循环完成，判断栈是否为空，如果不为空，则依次弹出栈中的元素，加入到表达式
while (seqStack.size() > 0){
Character pop = seqStack.pop();
sb.append(pop);
}
System.out.println(sb.toString());
}
private static boolean isTopElementHigher(Character opera, Character topElement) {
if (topElement.equals('*') || topElement.equals('/')){
return true;
}
if (topElement.equals('+') || topElement.equals('-')){
//若栈顶元素是+-，当前操作符也是+-，返回true，若栈顶元素是+-，当前操作符是*/，则不应弹栈，应将当前操作符入栈
if (opera.equals('+') || opera.equals('-')){
return true;
}
return false;
}
return false;
}
}