表达式求值

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */
#include <stdio.h>
#include <string.h>
int solve(char* s ) {
    // write code here
    char stack_ops[103];//符号栈
    int stack_val[103];//值栈
    int n = strlen(s);
    int top_val = 0;
    int top_ops = 0;
    int val = 0;
    for (int i = 0; i < n; i++) {
        //取数、存数
        if (s[i] >= '0' && s[i] <= '9') {
            val = 0;
            while (s[i] >= '0' && s[i] <= '9') {
                val = val * 10 + s[i] - '0';
                i++;
            }
            i--;
            stack_val[top_val++] = val;
        }
        //符号
        else {
            //若识别到')'，则将最近一个'('到此')'的所有字符出栈，消灭这一对括号
            if (s[i] == ')') {
                while (stack_ops[top_ops - 1] != '(') {
                    int x = stack_val[--top_val];
                    int y = stack_val[--top_val];
                    //注意，此时经过其他步骤，括号里只有一个运算符，可直接运算
                    if (stack_ops[top_ops-1] == '+') {
                        stack_val[top_val++] = x + y;
                    } else if (stack_ops[top_ops-1] == '-') {
                        stack_val[top_val++] = y - x;
                    } else if (stack_ops[top_ops-1] == '*') {
                        stack_val[top_val++] = y * x;
                    }
                    top_ops--;
                }
                top_ops--;
            }
            //若识别到('，入栈
            else if(s[i]=='(')
            {
                stack_ops[top_ops++]='(';
            }
             //若识别到'+'，判断优先级，如果栈顶运算符优先级较高，则将其出栈，并
             //进行运算
            else if (s[i]=='+'&&top_val>=2&&stack_ops[top_ops-1]=='*') {
                while (s[i]=='+'&&top_val>=2&&stack_ops[top_ops-1]=='*') {
                    int x = stack_val[--top_val];
                    int y = stack_val[--top_val];
                    stack_val[top_val++] = y*x;
                    top_ops--;
                }
                stack_ops[top_ops++]='+';
            }
            //若识别到'+'，看是否为连续加
            else if (s[i]=='+'&&top_val>=2&&stack_ops[top_ops-1]=='+') {
                while (s[i]=='+'&&top_val>=2&&stack_ops[top_ops-1]=='+') {
                    int x = stack_val[--top_val];
                    int y = stack_val[--top_val];
                    stack_val[top_val++] = y+x;
                    top_ops--;
                }
                stack_ops[top_ops++]='+';
            }
            //若识别到'-'，判断优先级，如果栈顶运算符优先级较高，则将其出栈，并
             //进行运算
            else if (s[i]=='-'&&top_val>=2&&stack_ops[top_ops-1]=='*') {
                while (s[i]=='-'&&top_val>=2&&stack_ops[top_ops-1]=='*') {
                    int x = stack_val[--top_val];
                    int y = stack_val[--top_val];
                    stack_val[top_val++] = y*x;
                    top_ops--;
                }
                stack_ops[top_ops++]='-';
            }
            //若识别到'-'，看是否为连续减
            //注意：连续减要从左往右算，这一步不可省略！！！，否则会出现从右往左减
            //的情况
            else if (s[i]=='-'&&top_val>=2&&stack_ops[top_ops-1]=='-') {
                while (s[i]=='-'&&top_val>=2&&stack_ops[top_ops-1]=='-') {
                    int x = stack_val[--top_val];
                    int y = stack_val[--top_val];
                    stack_val[top_val++] = y-x;
                    top_ops--;
                }
                stack_ops[top_ops++]='-';
            }
            else {
                stack_ops[top_ops++]=s[i];
            }
        }
    }
    //剩下的运算符直接运算
    while (top_ops!=0) {
        int x = stack_val[--top_val];
        int y = stack_val[--top_val];
        if(stack_ops[top_ops-1]=='+')
        {
            stack_val[top_val++] = y+x;
        }
        else if (stack_ops[top_ops-1]=='-') {
            stack_val[top_val++] = y-x;
        }
        else if (stack_ops[top_ops-1]=='*') {
            stack_val[top_val++] = y*x;
        }
        top_ops--;
    }
    return stack_val[0];
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 100

typedef struct my_stack {
    int arry[MAX_LEN];
    int top;
} my_stack;

typedef struct my_stack_fuhao {
    char arry[MAX_LEN];
    int top;
} my_stack_fuhao;

void init_my_stack(my_stack* s) {
    s->top = -1;
}

void init_my_stack_fuhao(my_stack_fuhao* s) {
    s->top = -1;
}

int is_empty(my_stack* s) {
    return s->top == -1;
}

int is_empty_fuhao(my_stack_fuhao* s) {
    return s->top == -1;
}

void push(my_stack* s, int val) {
    if (s->top < MAX_LEN - 1) {
        //printf("push: %d, s->top: %d\n", val, s->top);
        s->arry[++s->top] = val;
    } else {
        printf("error: stack overflow\n");
    }
}

void push_fuhao(my_stack_fuhao* s, char val) {
    if (s->top < MAX_LEN - 1) {
        s->arry[++s->top] = val;
    } else {
        printf("error: stack overflow\n");
    }
}

int top(my_stack* s) {
    if (!is_empty(s)) {
        return s->arry[s->top];
    } else {
        return 0;
    }
}

char top_fuhao(my_stack_fuhao* s) {
    if (!is_empty_fuhao(s)) {
        return s->arry[s->top];
    } else {
        return 0;
    }
}

int pop(my_stack* s) {
    if (!is_empty(s)) {
        return s->arry[s->top--];
    } else {
        return 0;
    }
}

char pop_fuhao(my_stack_fuhao* s) {
    if (!is_empty_fuhao(s)) {
        return s->arry[s->top--];
    } else {
        return 0;
    }
}

int youxianji_3(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*') return 2;
    return 0;
}

int applyOperation(int a, int b, char op) {
    switch (op) {
        case '+':
            printf("a=%d b=%d\n", a, b);
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
    }
    return 0;
}

int solve(char* s ) {
    // write code here
    int sum = 0, m, n, p, q;
    int num1 = 0, num2 = 0;
    int len;
    my_stack* haha = (my_stack*)malloc(sizeof(my_stack));
    my_stack_fuhao* fuhao = (my_stack_fuhao*)malloc(sizeof(my_stack_fuhao));
    len = strlen(s);

    init_my_stack(haha);
    init_my_stack_fuhao(fuhao);

    for (int i = 0; i < len; i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            int num = 0;
            while (i < len && (s[i] >= '0' && s[i] <= '9')) {
                printf("s[%d] = %d\n", i, (s[i]-'0'));
                num = num * 10 + (s[i] - '0');
                i++;
            }
            i--;
            printf("i=%d num=%d\n", i, num);
            push(haha, num);
        } else if (s[i] == '(') {
            push_fuhao(fuhao, s[i]);
        } else if (s[i] == ')') {
            while (top_fuhao(fuhao) != '(') {
                int val2 = pop(haha);
                int val1 = pop(haha);
                char op = pop_fuhao(fuhao);
                int result = applyOperation(val1, val2, op);
                push(haha, result);
            }
            pop_fuhao(fuhao);
        } else {   //运算符号
            printf("%c %d %d, %d\n", s[i], top_fuhao(fuhao), youxianji_3(top_fuhao(fuhao)), youxianji_3(s[i]));
            while (youxianji_3(top_fuhao(fuhao)) >= youxianji_3(s[i])) {
                printf("%c", s[i]);
                int val2 = pop(haha);
                int val1 = pop(haha);
                char op = pop_fuhao(fuhao);
                int result = applyOperation(val1, val2, op);
                push(haha, result);
            }
            push_fuhao(fuhao, s[i]);
        }
    }

    while (!is_empty_fuhao(fuhao)) {
        printf("xiaobo here\n");
        int val2 = pop(haha);
        int val1 = pop(haha);
        char op = pop_fuhao(fuhao);
        int result = applyOperation(val1, val2, op);
        printf("val1=%d val2=%d op=%c, result=%d\n", val1, val2, op, result);
        printf("xiaobo 01 %d\n", haha->top);
        push(haha, result);
        printf("xiaobo 01 %d, result=%d, %d\n", haha->top, haha->arry[haha->top], haha->arry[1]);
    }
    return top(haha);
}

using namespace std;
typedef int Status;
typedef char SElemType;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;
//初始化 
Status InitStack(SqStack &S)
{
    S.base=new SElemType[MAXSIZE];
    if(!S.base) exit(OVERFLOW);
    S.top=S.base;
    S.stacksize=MAXSIZE;
    return OK;
}
//入栈 
Status Push(SqStack &S,SElemType e)
{
    if(S.top-S.base==S.stacksize)
        return ERROR;
    *S.top++=e;
    return OK;
}
//出栈 
Status Pop(SqStack &S,SElemType &e)
{
    if(S.top==S.base)
        return ERROR;
    e=*--S.top;
    return OK;
}
//返回栈顶元素，不修改栈顶指针 
SElemType GetTop(SqStack S)
{
    if(S.top!=S.base)
    return *(S.top-1);
} 
//判断是否是运算符
Status In(SElemType e)
{
    if(e=='+'||e=='-'||e=='*'||e=='/'||e=='('||e==')'||e=='#')
        return OK;
    else return ERROR;
} 
//判断运算符的优先级 
SElemType Precede(char a,char b)
{
    char f;
    if(a=='+'||a=='-')
    {
        if(b=='+'||b=='-'||b==')'||b=='#')
            f='>';
        else if(b=='*'||b=='/'||b=='(')
            f='<';
    }
    else if(a=='*'||a=='/')
    {
        if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='#')
            f='>';
        else if(b=='(')
            f='<';
    }
    else if(a=='(')
    {
        if(b=='+'||b=='-'||b=='*'||b=='/'||b=='(')
            f='<';
        else if(b==')')
            f='=';
    }
    else if(a==')')
    {
        if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='#')
            f='>';
    }
    else if(a=='#')
    {
        if(b=='+'||b=='-'||b=='*'||b=='/'||b=='(')
            f='<';
        else if(b=='#')
            f='=';
    }
    return f;
}
//计算结果 
Status Operate(int i,char theta,int j)
{
    int result;
    switch(theta)
    {
        case '+':
            result=i+j;
            break;
        case '-':
            result=i-j;
            break;
        case '*':
            result=i*j;
            break;
        case '/':
            result=i/j;
            break;
    }
    return result;
}
SElemType EvaluateExpression()
{
    SqStack OPTR,OPND;
    char ch;
    char a,b,theta,x;
    InitStack(OPTR);
    Push(OPTR,'#');
    InitStack(OPND);
    ch=getchar();
    while(ch!='#'||GetTop(OPTR)!='#')
    {
        cin>>ch;
        if(!In(ch))
        {
            Push(OPND,ch);
            ch=getchar();
        }
        else{
            switch(Precede(GetTop(OPTR),ch)){
                case '<':
                    Push(OPTR,ch);
                    ch=getchar();
                    break;
                case '>':
                    Pop(OPTR,theta);
                    Pop(OPND,b);
                    Pop(OPND,a);
                    Push(OPND,Operate(a,theta,b));
                    break;
                case '=':
                    Pop(OPTR,x);
                    ch=getchar();
                    break;
            }
        }
    }
    return GetTop(OPND);
}
int main()
{
        cout<<"输入表达式（以#结束）："<<endl;
        EvaluateExpression();
        cout<<Operate<<endl;
        return 0;
}

int GetInt(char **s) {
    int res=0;
    bool GetInt = false;
    while((**s)!=0) {
        if((**s)>='0' && (**s)<='9') {
            res *=10;
            res += ((**s)-'0');
            (*s)++;
            GetInt = true;
        }
        else {
            if(GetInt) 
               break;
            else 
               (*s)++;
                
        }
    }
    return res;
}

int bracketLen(char *s) {
    int len=0;
    if(s[0]!='(')
        return 0;
    else {
        s++;
        while(1) {
            char c = s[len];
            if(c=='(') {
                len += bracketLen(s+len)+2;
                continue;
            }
            else if(c==')' || c==0) 
                break;
            len++;
        }
        
    }
    return len;
}

int solve(char* s ) {
    #define push(a) stack[pointStack++] = a
    #define pop()   stack[--pointStack]

    int stack[100]={0}, pointStack=0;
    int res=0;
    char *p=s;
    bool firstFlag = true;
    while(*p) {
        if(*p=='(') {
            char *buffer;
            int BKval;
            int BKLen = bracketLen(p);
            buffer = (char*)malloc(BKLen+1);
            strncpy(buffer, p+1, BKLen);
            buffer[BKLen] = 0;
            BKval = solve(buffer);
            if(!firstFlag) {
                if(*(p-1)=='-')
                    push(-BKval);
                else if(*(p-1)=='+')
                    push(BKval);
                else if(*(p-1)=='*') 
                    push(pop()*BKval);  
            }
            else
                push(BKval);
            firstFlag = false;
            p += BKLen+strlen("()");
        }
        else if(*p>='0' && *p<='9') {
            if(!firstFlag) {
                if(*(p-1)=='-')
                    push(-GetInt(&p));
                else if(*(p-1)=='+')
                    push(GetInt(&p));
                else if(*(p-1)=='*')
                    push(pop()*GetInt(&p));    
            }
            else
                push(GetInt(&p));
            firstFlag = false;
        }
        else if(*p=='+' || *p=='-') {
            while(pointStack) 
                res += pop();
            p++;
        }
        else if(*p=='*' || *p==')') 
            p++;
    }
    while(pointStack) {
        res += pop();
    }
    return res;
}

/*
支持加减乘括号运算，"2*(3+4)"
1.建立两个栈，一个存数字，一个存运算符；
2.对于数字直接进栈，对于运算符，当前运算符大于栈顶运算符时入栈，否则从数栈中弹出两个数进行运算。
3.注意：字符串遍历完，同时运算符栈为空时，计算才结束；对于数字要循环读取字符直至运算符；
*/
int isOperator(char c){
	if(c=='(' || c==')' || c=='+' || c=='-' || c=='*')
		return 1;
	else
		return 0;
}
/*
运算符优先级比较一定考虑哪个在左边哪个在右边，
a ? b （a在左边，b在右边，即a是已经进栈字符,b是当前字符）
a,b ( ) + - *
(   < = < < < 
)   ? > > > >
+   < > > > <
-   < > > > <
*   < > > > >
*/
char getCmp(char a,char b){//a在左边，b在右边
	if(a=='('){
		if(b==')')
			return '=';
		return '<';
	}else if(a==')'){
		return '>';
	}else if(a=='+' || a=='-'){
		if(b=='(' || b=='*')
			return '<';
		return '>';
	}else{//a=='*'
		if(b=='(')
			return '<';
		return '>';
	}
}
int cal(int a,int b,char op){
	if(op=='+')
		return a+b;
	else if(op=='-')
		return a-b;
	else
		return a*b;
}
int solve(char* s ) {
	int stk_num[100];
	char stk_op[100],op;
	int top_num=0,top_op=0,i=0,a,b;
	while(s[i]!='\0'|| top_op!=0){
		if(s[i]!='\0' && isOperator(s[i])==1){//是运算符
			if(top_op==0 || getCmp(stk_op[top_op-1],s[i])=='<'){//当前运算符优先级较大，压栈
				stk_op[top_op++]=s[i];
				i++;
			}else if(getCmp(stk_op[top_op-1],s[i])=='>'){//弹栈，进行运算
				op=stk_op[--top_op];
				b=stk_num[--top_num];
				a=stk_num[--top_num];
				stk_num[top_num++]=cal(a,b,op);//计算后再压栈
			}else{//消掉左右括号
				top_op--;
				i++;
			}
		}else if(s[i]=='\0'){//字符全部压入栈，弹栈
			while(top_op!=0){//内循环弹运算符栈，不用走大循环
				b=stk_num[--top_num];
				a=stk_num[--top_num];
				op=stk_op[--top_op];
				stk_num[top_num++]=cal(a,b,op);//计算后再压栈	
			}		
		}else{//是操作数
			int x=0;
			while(s[i]!='\0' && isOperator(s[i])!=1){//循环读取n位数，构成一个操作数
				x=x*10+s[i]-'0';
				i++;
			}
			stk_num[top_num++]=x;
		}
	}//while
	return stk_num[0];
}